Bảng số B (Tin học trẻ toàn quốc 2025 – Vòng chung kết toàn quốc – Bảng B)
Đề bài
Xét một bảng vuông $n \times n$, mỗi ô hoặc để trống, hoặc ghi số $1$, hoặc ghi số $2$. Bảng được gọi là đẹp nếu thoả mãn cả hai điều kiện:
- Mỗi hàng và mỗi cột có đúng một số $1$, đúng một số $2$, còn lại $n - 2$ ô trống.
- Đi theo đường xoắn ốc bắt đầu từ ô góc trên bên trái, đi sang phải trước rồi vòng dần vào trong theo chiều kim đồng hồ, các số gặp được (bỏ qua ô trống) lần lượt là $1, 2, 1, 2, \ldots$
Hình dưới là một bảng đẹp $4 \times 4$ (đường nét đứt là đường xoắn ốc):
Cho $n$, hãy xây dựng một bảng đẹp kích thước $n \times n$.
Dữ liệu vào: một số tự nhiên $n$ $(2 \le n \le 200)$.
Kết quả: nếu có bảng đẹp, in $n$ dòng, mỗi dòng $n$ số cách nhau một dấu cách, ô trống ghi là $0$. Nếu không có, in một dòng -1. Có nhiều bảng đúng thì in bảng nào cũng được.
Subtask:
- Subtask 1 ($50\%$ số điểm): $n \le 15$.
- Subtask 2 ($50\%$ số điểm): không có ràng buộc gì thêm.
Giới hạn thời gian: 1 giây. Dữ liệu nhập từ bàn phím, in ra màn hình.
40 0 1 2
2 1 0 0
1 0 2 0
0 2 0 1Lưu ý: bài có nhiều đáp án, bảng mà code ở dưới in ra cho $n = 4$ khác bảng trong ví dụ nhưng vẫn là một bảng đẹp.
Lời mở đầu
Đây là kiểu bài "xây dựng" (constructive): không có công thức nào để "tính" đáp án, ta phải tự nghĩ ra một cách xếp số luôn đúng. Hướng tiếp cận rất hay dùng: (1) viết quay lui tìm bảng cho $n$ nhỏ để có điểm subtask 1, (2) nhìn vào các bảng tìm được để đoán quy luật, (3) chứng minh quy luật đúng cho mọi $n$. Mình đi đúng 3 bước đó.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test có gì?
Bộ test trên CLUE gồm 20 test (mình tự sinh theo đúng tỉ lệ subtask), mỗi test chỉ là một số $n$:
| Nhóm | Test | Các giá trị $n$ |
|---|---|---|
| Subtask 1 (50%) | 1–10 | 4, 2, 3, 5, 6, 7, 8, 12, 14, 15 |
| Subtask 2 (50%) | 11–20 | 16, 17, 66, 99, 100, 128, 171, 198, 199, 200 |
- Test 1 là ví dụ của đề ($n = 4$). Có cả $n$ chẵn lẫn lẻ, nhỏ nhất $n = 2$, lớn nhất $n = 200$.
- Như sẽ chứng minh ở dưới, mọi $n \ge 2$ đều có bảng đẹp nên không có test nào phải in
-1. - Bài có nhiều đáp án đúng, nên CLUE chấm bằng một chương trình kiểm tra (checker): đọc bảng em in ra và kiểm tra đủ 2 điều kiện, chứ không so khớp với một đáp án cố định. Bảng em in ra khác ví dụ của đề vẫn được tính đúng.
Kết quả chạy thật (C++, chấm bằng checker) theo từng subtask:
| Subtask | Điều kiện | Test | Cách 1 quay lui | Cách 2 đặt 4 góc |
|---|---|---|---|---|
| Subtask 1 (50%) | $n \le 15$ | 1–10 | qua | qua |
| Subtask 2 (50%) | $n \le 200$ | 11–20 | 3/10 test | qua |
Lời giải "ghép khung" (cùng ý tưởng cách 2) mình đã nộp thử trên hệ thống chấm chính thức của hội thi (tinhoctre.vn) và đạt AC 100/100 điểm.
Cách 1Quay lui theo đường xoắn ốc
Điều kiện 2 nói về thứ tự xoắn ốc, nên ta điền bảng theo đúng thứ tự đó: liệt kê các ô theo đường xoắn ốc vào mảng ord, rồi lần lượt quyết định từng ô. Nhờ vậy điều kiện 2 tự động thoả: ta chỉ cần nhớ số cần đặt tiếp theo $x$ (bắt đầu là $1$, đặt xong $1$ thì tới $2$, đặt xong $2$ thì tới $1$).
Với ô thứ idx trên đường xoắn ốc, có 2 lựa chọn:
- Đặt số $x$ – chỉ được nếu hàng và cột của ô chưa có số $x$.
- Để trống – chỉ được nếu sau khi bỏ qua ô này, hàng và cột vẫn còn đủ chỗ để có đủ 2 số. Ta giữ
demR[r]= số ô đã điền số trên hàng $r$ vàconR[r]= số ô chưa xét trên hàng $r$; điều kiện làdemR[r] + conR[r] >= 2(tương tự với cột). Đây là cắt nhánh quan trọng giúp quay lui chạy nhanh.
Khi đã xét hết các ô thì mọi hàng, cột chắc chắn có đủ một số 1 và một số 2 (không bao giờ có 2 số giống nhau, và nhờ cắt nhánh mỗi hàng/cột có đủ 2 số).
- Thứ tự thử: đặt số trước, để trống sau – giúp tìm thấy bảng sớm hơn.
conR[r]--; conC[c]--;ở đầu hàm: ô $(r, c)$ đang được xét nên không còn là ô "chưa xét". Khi quay lui (trả về false) phải cộng lại.- Số cần đặt tiếp theo sau $x$ là $3 - x$ (1 → 2, 2 → 1).
Kết quả chạy thật: bản C++ đúng 13/20 test – quá thời gian test 14–20 (test đúng chạy lâu nhất 0,411 giây). Bản Python đúng 12/20 test – quá thời gian test 13–20 (test đúng chạy lâu nhất 0,040 giây). Quay lui có cắt nhánh qua trọn subtask 1 (thậm chí chạy được tới $n = 66$), nhưng $n$ cỡ 100 – 200 thì không kịp.
Ý tưởngNhìn bảng quay lui tìm ra, đoán quy luật
Thử in bảng cho $n = 2$ và $n = 3$ (chính là kết quả của cách 1):
Bảng $2 \times 2$ là 4 góc: trên trái 1, trên phải 2, dưới phải 1, dưới trái 2 – đi xoắn ốc gặp đúng $1, 2, 1, 2$. Từ đó nảy ra ý: với bảng $n \times n$, chỉ đặt số ở 4 góc của vành ngoài cùng theo đúng mẫu này, rồi phần bên trong là một bảng đẹp $(n - 2) \times (n - 2)$:
- Hàng/cột ngoài cùng: hàng trên có 1 (góc trái) và 2 (góc phải); hàng dưới có 2 và 1; cột trái có 1 và 2; cột phải có 2 và 1 – mỗi hàng/cột đúng một số 1, một số 2. Các hàng/cột bên trong có 2 ô ở vành ngoài đều trống, nên chỉ phụ thuộc bảng bên trong.
- Thứ tự xoắn ốc: đường xoắn ốc đi hết vành ngoài trước (gặp 4 góc theo thứ tự trên trái → trên phải → dưới phải → dưới trái, tức $1, 2, 1, 2$) rồi mới vào trong, và đi bên trong giống hệt đường xoắn ốc của bảng $(n-2) \times (n-2)$ – bắt đầu lại bằng $1$. Hoàn hảo!
Vậy mọi $n \ge 2$ đều có bảng đẹp, đáp án -1 không bao giờ xảy ra. Em nhập $n$ rồi bấm Tiếp để xem từng vành được đặt góc:
Cách 2Đặt 4 góc cho từng vành – O(n²)
- Vành thứ $d$ có cạnh $s = n - 2d$, góc trên trái ở $(d, d)$, góc dưới phải ở $(n-1-d,\ n-1-d)$.
- Điều kiện lặp
n - 2 * d >= 2 && n - 2 * d != 3: còn vành cỡ ít nhất 2 và chưa phải lõi $3 \times 3$. Với $n$ chẵn, vòng lặp dừng khi $s = 0$; với $n$ lẻ dừng khi $s = 3$ và điền lõi. - Ghi chú: lời giải đã nộp lên hệ thống chấm chính thức viết tổng quát hơn (dùng quay lui cho $n \le 10$ rồi "ghép khung"), nhưng bản chất giống hệt cách 2 – ở bài Bảng số C (bảng C2) mình sẽ dùng lại kiểu ghép khung đó cho trường hợp 3 số.
Kết quả chạy thật: bản C++ đúng 20/20 test, chậm nhất 0,005 giây. Bản Python đúng 20/20 test, chậm nhất 0,024 giây.
Nhận xét
Đăng nhận xét