THT B Vòng Sơ loại Toàn quốc 2025 - Lần 1

Một số nguyên dương được gọi là số đẹp nếu tổng các chữ số chia hết cho \(9\). Ví dụ, số \(9, 18, 2007\) là các số đẹp.

Yêu cầu: Cho số nguyên dương \(n\), tính tổng các số đẹp không vượt quá \(n\).

Input

• Gồm một dòng chứa số nguyên \(n\) (\(n \le 10^9\)).

Output

• Gồm một dòng chứa một số nguyên là tổng tính được.

Example

20

27

Scoring

• Có \(80\%\) số test có \(n \le 10^6\).
• Có \(20\%\) số test còn lại không có ràng buộc nào thêm.

Bảng vuông gần nguyên tố

Giả sử \(A\) là lưới ô vuông gồm \(m\) dòng và \(n\) cột. Các dòng của lưới được đánh số từ \(1\) đến \(m\), từ trên xuống dưới. Các cột của lưới được đánh số từ \(1\) đến \(n\), từ trái sang phải. Ô nằm trên giao của dòng \(i\) (\(1 \le i \le m\)) và cột \(j\) (\(1 \le j \le n\)) của lưới gọi là ô \((i, j)\) được điền số nguyên không âm \(a_{i,j}\) (\(a_{i,j} \le 10^6\)).

Một hình vuông gồm các ô nằm trong lưới \(A\) được gọi là bảng vuông gần nguyên tố nếu có không quá một ô trong hình vuông chứa số không phải là số nguyên tố.

Yêu cầu: Cho \(m, n\) và các số được điền trên lưới \(A\), hãy tìm bảng vuông gần nguyên tố có diện tích lớn nhất.

Input

• Dòng đầu chứa hai số nguyên \(m, n\).
• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa \(n\) số nguyên không âm \(a_{i,1}, a_{i,2}, \dots, a_{i,n}\).

Output

• Gồm một số nguyên là số ô trong bảng vuông gần nguyên tố tìm được.

Example

3 4
1 2 3 4
1 3 5 7
2 4 6 8

4

Ràng buộc

• Có \(25\%\) số test có \(m, n \le 10\).
• Có \(25\%\) số test khác có \(m, n \le 50\).
• Có \(25\%\) số test khác có \(m, n \le 300\).
• Có \(25\%\) số test còn lại có \(m \cdot n \le 10^6\).

Biến đổi

Cho dãy số nguyên không âm \(a_1, a_2, \dots, a_n\) (\(4 \le n \le 8\); \(a_i \le 10^9\)). Cần biến đổi dãy để tất cả các phần tử đều bằng \(0\). Mỗi bước được phép chọn \(4\) phần tử liên tiếp \(a, b, c, d\) biến đổi thành \(|a - b|, |b - c|, |c - d|, |d - a|\).

Ví dụ:
0 1 3 5 9
0 2 2 4 8 (1)
0 0 2 4 6 (2)
0 2 2 2 6 (3)
0 0 0 4 4 (4)
0 0 4 0 4 (5)
0 4 4 4 4 (6)
0 0 0 0 0 (7)

Yêu cầu: Hãy tính số phép biến đổi ít nhất cần thực hiện để tất cả các phần tử đều bằng \(0\).

Input

• Gồm một số dòng, mỗi dòng chứa một số nguyên là các phần tử của dãy \(a_1, a_2, \dots, a_n\).

Output

• Ghi số phép biến đổi ít nhất cần thực hiện để tất cả các phần tử đều bằng \(0\).

Example

0
1
3
5
9

7

Ràng buộc

• Có \(30\%\) số điểm tương ứng với \(n = 4\).
• Có \(30\%\) số điểm khác tương ứng với \(n \le 6\).
• \(40\%\) số điểm còn lại không có ràng buộc nào thêm.

Cho một hình chữ nhật kích thước \(N \cdot M\) trên hệ trục với bốn đỉnh có tọa độ lần lượt là \((0, 0), (0, N), (M, 0), (M, N)\). Tại thời điểm \(0\), có một quả bóng được ném đi từ vị trí \((0,0)\) theo hướng của vector \(d = (d_x, d_y)\) và quả bóng bay với vận tốc cố định, cụ thể, mỗi giây quả bóng sẽ di chuyển từ vị trí \((x, y)\) đến vị trí \((x + d_x, y + d_y)\).

Khi chạm vào cạnh hoặc góc của hình chữ nhật, thì quả bóng sẽ nảy ra và thay đổi hướng di chuyển như sau:

• Nếu như quả bóng chạm vào cạnh \(y = 0\) hoặc \(y = N\), thì vector hướng \((d_x, d_y)\) sẽ trở thành \((d_x, -d_y)\);
• Nếu như quả bóng chạm vào cạnh \(x = 0\) hoặc \(x = M\), thì vector hướng \((d_x, d_y)\) sẽ trở thành \((-d_x, d_y)\);
• Nếu như quả bóng chạm vào một trong bốn góc kể trên, thì vector hướng \((d_x, d_y)\) sẽ trở thành \((-d_x, -d_y)\).

Giả sử rằng quả bóng là một điểm và luôn giữ vận tốc cố định (năng lượng của quả bóng không bị mất đi). Hãy cho biết từ thời điểm \(0\) đến thời điểm \(T\), quả bóng đã chạm vào cạnh của hình chữ nhật bao nhiêu lần, giả sử rằng chạm góc được tính là hai lần chạm cạnh. Lưu ý, vị trí \((0, 0)\) ban đầu không được tính là một lần chạm.

Input

• Gồm một dòng duy nhất chứa năm số nguyên \(N, M, T, d_x, d_y\) (\(0 < N, M, T \leq 10^9\); \(0 \leq d_x, d_y \leq 10^9\)).

Output

• Gồm một dòng duy nhất chứa một số nguyên là số lần quả bóng chạm cạnh.

Example

5 5 100 1 1

40

Scoring

• Có \(20\%\) số điểm tương ứng với \(T \leq 10^5\).
• Có \(20\%\) số điểm khác tương ứng với \(N, M \leq 10^3\).
• Có \(20\%\) số điểm khác tương ứng với \(d_x = d_y = 1\).
• Có \(20\%\) số điểm khác tương ứng với \(d_x = 0\) hoặc \(d_y = 0\).
• \(20\%\) số điểm còn lại không có ràng buộc nào thêm.

Khi giảng dạy về vector, Alice đã tạo ra \(n\) vector, vector thứ \(i\) (\(1 \le i \le n\)) là \((x_i, y_i, z_i)\). Để học sinh luyện tập về tổng các vector, cô bí mật chọn ra một số vector, tính tổng để nhận được vector \((x, y, z)\) sau đó yêu cầu học sinh tìm ra một phương án chọn các vector để tổng các vector là vector \((x, y, z)\).

Yêu cầu: Cho \(n\) vector và ba số \(x, y, z\), hãy giúp Alice đưa ra một cách chọn thỏa mãn.

Input

• Dòng đầu chứa bốn số nguyên \(n, x, y, z\) (\(n \le 200; 0 \le x, y, z \le 10^6\));
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên không âm \(x_i, y_i, z_i\) (\(0 \le x_i, y_i, z_i \le 10^6\));

Output

• Đưa ra một xâu gồm \(n\) kí tự, kí tự thứ \(i\) bằng 1 hoặc bằng 0 tương ứng là chọn hay không chọn vector thứ \(i\).

Example

3 1 2 3
1 1 1
1 0 1
0 1 2

101

Scoring

• Có \(25\%\) số test có \(n \le 20\);
• Có \(25\%\) số test khác có \(n \le 40\);
• Có \(25\%\) số test khác có \(y_i = z_i = 0\) với mọi \(1 \le i \le n\);
• Có \(25\%\) số test còn lại không có ràng buộc nào thêm.