Độ khó: Trung bình (2/4 điểm)

Cho lưới ô vuông ~A~ gồm ~m~ dòng và ~n~ cột. Các dòng được đánh số từ ~1~ đến ~m~ theo thứ tự từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~n~ theo thứ tự từ trái sang phải. Ô ở dòng ~i~, cột ~j~ ~(1 \le i \le m,\ 1 \le j \le n)~ được gọi là ô ~(i, j)~ và chứa 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 ô của lưới được gọi là bảng vuông gần nguyên tố nếu trong hình vuông đó có không quá một ô chứa số không phải số nguyên tố.

Hãy tìm bảng vuông gần nguyên tố có diện tích lớn nhất và cho biết nó gồm bao nhiêu ô.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương ~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}, \ldots, a_{i,n}~.

Kết quả

Một số nguyên duy nhất là số ô của bảng vuông gần nguyên tố lớn nhất.

Subtask

• Subtask 1 (~25\%~ số test): ~m, n \le 10~.
• Subtask 2 (~25\%~ số test): ~m, n \le 50~.
• Subtask 3 (~25\%~ số test): ~m, n \le 300~.
• Subtask 4 (~25\%~ số test): ~m \times n \le 10^6~.

Sample Input 1

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

Sample Output 1

4

Giải thích

Hình vuông ~2 \times 2~ gồm các ô ~(1,2), (1,3), (2,2), (2,3)~ chứa các số ~2, 3, 3, 5~ đều là số nguyên tố. Không có hình vuông ~3 \times 3~ nào chứa ít hơn hai số không nguyên tố, nên đáp án là ~4~.

Nguồn: Tin học trẻ 2025 – Vòng loại quốc gia đợt 1 – Bảng B; Vòng loại quốc gia đợt 1 – Bảng C1; Vòng loại quốc gia đợt 1 – Bảng C2.

Độ khó: Trung bình (2/4 điểm)

Trên mặt phẳng toạ độ cho hình chữ nhật kích thước ~N \times M~ có bốn đỉnh ~(0, 0)~, ~(0, N)~, ~(M, 0)~, ~(M, N)~. Tại thời điểm ~0~, một quả bóng được ném từ điểm ~(0, 0)~ theo hướng vector ~d = (d_x, d_y)~. Bóng chuyển động với vận tốc không đổi: sau mỗi giây, bóng đi từ vị trí ~(x, y)~ tới vị trí ~(x + d_x, y + d_y)~.

Khi bóng chạm cạnh hoặc góc của hình chữ nhật, nó nảy lại và đổi hướng như sau:

• Chạm cạnh ~y = 0~ hoặc ~y = N~: vector hướng ~(d_x, d_y)~ trở thành ~(d_x, -d_y)~;
• Chạm cạnh ~x = 0~ hoặc ~x = M~: vector hướng ~(d_x, d_y)~ trở thành ~(-d_x, d_y)~;
• Chạm một trong bốn góc: vector hướng ~(d_x, d_y)~ trở thành ~(-d_x, -d_y)~.

Coi quả bóng là một điểm và vận tốc của nó không bao giờ thay đổi về độ lớn. Hãy đếm số lần bóng chạm cạnh của hình chữ nhật trong khoảng thời gian từ thời điểm ~0~ đến thời điểm ~T~, biết rằng mỗi lần chạm góc được tính là hai lần chạm cạnh, và vị trí xuất phát ~(0, 0)~ không được tính là một lần chạm.

Dữ liệu vào

Một dòng gồm năm số nguyên ~N, M, T, d_x, d_y~ ~(0 < N, M, T \le 10^9;\ 0 \le d_x, d_y \le 10^9)~.

Kết quả

Một số nguyên là số lần bóng chạm cạnh.

Subtask

• Subtask 1 (~20\%~ số điểm): ~T \le 10^5~.
• Subtask 2 (~20\%~ số điểm): ~N, M \le 10^3~.
• Subtask 3 (~20\%~ số điểm): ~d_x = d_y = 1~.
• Subtask 4 (~20\%~ số điểm): ~d_x = 0~ hoặc ~d_y = 0~.
• Subtask 5 (~20\%~ số điểm): không có ràng buộc gì thêm.

Sample Input 1

5 5 100 1 1

Sample Output 1

40

Giải thích

Bóng đi dọc đường chéo của hình vuông ~5 \times 5~, cứ sau ~5~ giây lại chạm một góc (tính ~2~ lần chạm). Trong ~100~ giây có ~20~ lần chạm góc, tức ~40~ lần chạm cạnh.

Nguồn: Tin học trẻ 2025 – Vòng loại quốc gia đợt 1 – Bảng C1; Vòng loại quốc gia đợt 1 – Bảng C2.

Độ khó: Khó (4/4 điểm)

Trong một giờ học về vector, cô 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 phép cộng vector, cô bí mật chọn ra một số vector trong đó, cộng chúng lại được vector ~(x, y, z)~, rồi yêu cầu học sinh tìm một cách chọn các vector sao cho tổng của chúng đúng bằng ~(x, y, z)~.

Cho ~n~ vector và ba số ~x, y, z~, hãy giúp Alice đưa ra một cách chọn thoả mãn. Dữ liệu đảm bảo luôn tồn tại cách chọn.

Dữ liệu vào

• 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 ~x_i, y_i, z_i~ ~(0 \le x_i, y_i, z_i \le 10^6)~.

Kết quả

Một xâu gồm ~n~ kí tự, kí tự thứ ~i~ là 1 nếu chọn vector thứ ~i~ và là 0 nếu không chọn. Nếu có nhiều cách chọn, in ra cách bất kỳ.

Subtask

• Subtask 1 (~25\%~ số test): ~n \le 20~.
• Subtask 2 (~25\%~ số test): ~n \le 40~.
• Subtask 3 (~25\%~ số test): ~y_i = z_i = 0~ với mọi ~1 \le i \le n~.
• Subtask 4 (~25\%~ số test): không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

101

Giải thích

Chọn vector thứ nhất và thứ ba: ~(1, 1, 1) + (0, 1, 2) = (1, 2, 3)~.

Nguồn: Tin học trẻ 2025 – Vòng loại quốc gia đợt 1 – Bảng C1.