Một số nguyên dương X gồm n chữ số dạng (a1a2...an ) có trọng số S(X) được tính theo công thức: S(X)=1xa1 + 2xa2 + ... + nxan. Ví dụ: X=2025 có trọng số là S(2025)=1x2+2x0+3x2+4×5=28.

Yêu cầu:

Cho số nguyên dương X trong đó có một chữ số bị mờ biểu diễn bằng dấu '?'. Hãy tìm chữ số có giá trị nhỏ nhất trong các chữ số từ '0' đến '9' để thay vào vị trí dấu '?' sao cho S(X) chia hết cho 7.

Dữ liệu:

Vào từ tệp CAU1.INP chứa số nguyên dương X (X < 10^100) trong đó có 1 chữ số bị mờ biểu diễn bằng dấu '?'.

Kết quả:

Ghi ra tệp CAU1.OUT một chữ số nhỏ nhất có thể thay vào dấu '?', nếu không tồn tại chữ số nào thoả mãn thì ghi -1. Số X không được chứa chữ số '0' vô nghĩa ở đầu.

Ví dụ 1:

CAU1.INP

202?

CAU1.OUT

5

Giải thích: Số 2025 có S(2025) = 28 chia hết cho 7.

Ví dụ 2:

CAU1.INP

?7

CAU1.OUT

7

Giải thích: Vì dấu '?' đứng đầu không thể thay bằng chữ số 0, nên X = 77 có S(77)= 21 chia hết cho 7.

Ví dụ 3:

CAU1.INP

800000?

CAU1.OUT

-1

Giải thích: Không có chữ số nào thay thế dấu '?' thoả mãn S(X) chia hết cho 7.

Một trường học có n học sinh, học sinh thứ i có độ hạnh phúc hi. Nếu hai học sinh i và j bắt tay nhau (i ≠ j, 1 ≤ i, j ≤ n) sẽ tạo ra độ hạnh phúc là hi×hj. Học sinh i và học sinh j chỉ được tính là bắt tay nhau một lần duy nhất.

Yêu cầu:

Tính tổng độ hạnh phúc của toàn trường nếu tất cả học sinh đều bắt tay nhau.

Dữ liệu:

Vào từ tệp CAU2.INP gồm: Dòng đầu là số nguyên n là số học sinh toàn trường (2≤n≤30000); Dòng tiếp theo chứa n số nguyên dương h1,h2,…,hn lần lượt là độ hạnh phúc của từng học sinh (0<hi≤30000).</p>

Kết quả:

Ghi ra tệp CAU2.OUT một số duy nhất là tổng độ hạnh phúc của toàn trường nếu tất cả học sinh đều bắt tay nhau.

Ví dụ:

CAU2.INP

4
2 5 1 2

CAU2.OUT

33

Giải thích: Tổng độ hạnh phúc là:2×5+2×1+2×2+5×1+5×2+1×2=33

Ràng buộc:

- Có 80% số test ứng với 80% số điểm của bài có n,h_i≤ 3000;
- Có 20% số test ứng với 20% số điểm của bài có n,h_i≤ 30000.

Vương quốc Băng giá có n^2 bông tuyết được đánh số từ 1 đến n^2. Bông tuyết thứ i có khối lượng ai. Elsa chạm vào một bông tuyết bất kì có khối lượng w thì lập tức tất cả các bông tuyết có cùng khối lượng w sẽ tan biến.

Yêu cầu:

Cho biết khối lượng của n^2 bông tuyết. Xác định tổng khối lượng lớn nhất của các bông tuyết chưa tan.

Dữ liệu:

Vào từ tệp văn bản CAU3.INP gồm:

- Dòng thứ nhất chứa số nguyên dương n;
- Dòng thứ hai chứa n^2  số nguyên dương a1,a2,...,a(n^2).

(0< n <= 1500,ai <= 10^9,1 <= i <= n^2)

Kết quả:

Ghi ra tệp CAU3.OUT một số nguyên duy nhất là giá trị lớn nhất của tổng khối lượng các bông tuyết chưa tan.

Ví dụ:

CAU3.INP

3
1 2 4 1 1 1 1 1 2

CAU3.OUT

10

Giải thích: - Chạm vào bông tuyết có khối lượng w=1, tổng khối lượng chưa tan là 2+4+2=8. - Chạm vào bông tuyết có khối lượng w=2, tổng khối lượng chưa tan là 1+4+1+1+1+1+1=10. - Chạm vào bông tuyết có khối lượng w=4, tổng khối lượng chưa tan là 1+2+1+1+1+1+1+2=10. Vậy tổng khối lượng lớn nhất chưa tan là 10.

Ràng buộc:

- Có 25% số test ứng với 25% số điểm của bài có n <= 50, 0<ai≤10^3;
- Có 25% số test ứng với 25% số điểm của bài có n <= 500, 0<ai≤10^6, các ai có giá trị phân biệt;
- Có 25% số test ứng với 25% số điểm của bài có n <= 500, 0<ai≤10^6;
- Có 25% số test ứng với 25% số điểm của bài có n <= 1500, 0<ai≤10^9.

Wednesday và các bạn bị nhốt vào một căn phòng với rất nhiều cạm bẫy. Tuy nhiên, là một người thông minh và dũng cảm, Wednesday đã giúp cả nhóm vượt qua được hầu như tất cả khó khăn để đến cửa ra của căn phòng. Ở cửa ra có một chiếc ổ khóa với kết cấu rất kì dị. Trên chiếc ổ khóa có m vòng khóa, mỗi vòng ghi n số nguyên (2≤m≤5;1≤n≤10^5). Vòng số thứ i sẽ chứa n số nguyên a(i,1);a(i,2);…;a(i,n) (|a(i,j)|≤10^9;1≤i≤m;1≤j≤n). Các vòng số có thể xoay tròn. Mỗi bước xoay, trên mỗi vòng số chỉ hiện đúng một số. Để mở được ổ khóa Wednesday cần phải xoay các vòng số sao cho tổng m số hiện trên m vòng số này đúng bằng S (|S|≤10^9).

Yêu cầu:

Cho các giá trị trên m vòng số, hãy giúp Wednesday đếm xem có bao nhiêu cách xoay để mở được ổ khóa này.

Dữ liệu:

Vào từ tệp CAU4.INP: Dòng đầu tiên ghi ba số nguyên m,n,S như mô tả ở đề bài. m dòng tiếp theo mỗi dòng ghi n số nguyên cho biết các giá trị trên từng vòng số.

Kết quả:

Ghi ra tệp CAU4.OUT một số nguyên duy nhất là số cách để mở được ổ khóa đặc biệt này.

Ví dụ 1:

CAU4.INP

2 3 5
1 2 1
3 4 4

CAU4.OUT

5

Ví dụ 2:

CAU4.INP

5 2 2
1 2
1 2
1 2
1 2
-2 -2

CAU4.OUT

2

Ràng buộc:

- Có 30% số test ứng với 30% số điểm của bài có m=2,n≤10^5;
- Có 40% số test ứng với 40% số điểm của bài có m=4,n≤10^3;
- Có 30% số test ứng với 30% số điểm của bài có m=5,n≤400.

Cho số nguyên tố k, tìm số nguyên dương m nhỏ nhất sao cho k×m tạo thành một số có tất cả các chữ số giống nhau.

Yêu cầu:

Tìm phần dư nhận được trong phép chia m cho 10^9+7.

Dữ liệu:

Vào từ tệp văn bản CAU5.INP một số nguyên tố k (1 ≤ k ≤ 10^9).

Kết quả:

Ghi ra tệp văn bản CAU5.OUT một số nguyên là đáp số của bài toán.

Ví dụ 1:

CAU5.INP

13

CAU5.OUT

8547

Ví dụ 2:

CAU5.INP

23

CAU5.OUT

797103822

Ràng buộc:

- Có 50% số test ứng với 50% số điểm của bài có k×m≤10^9;
- Có 50% số test ứng với 50% số điểm của bài không có ràng buộc gì thêm.