Bảng số C (Tin học trẻ toàn quốc 2025 – Vòng chung kết toàn quốc – Bảng C2)
Đề bài
Xét một bảng vuông $n \times n$, mỗi ô hoặc để trống, hoặc ghi một số nguyên từ $1$ đến $k$ ($k \le n$). Bảng được gọi là $k$-đẹp nếu thoả mãn đồng thời:
- Mỗi hàng và mỗi cột có đúng $n - k$ ô trống.
- Trên mỗi hàng và mỗi cột, mỗi số $x$ ($1 \le x \le k$) xuất hiện đúng một lần.
- Đi theo đường xoắn ốc bắt đầu từ ô góc trên bên trá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, \ldots, k, 1, 2, \ldots, k, \ldots$
Hình dưới là một bảng $2$-đẹp $4 \times 4$ (đường nét đứt là đường xoắn ốc):
Cho $n$ và $k$, hãy xây dựng một bảng $k$-đẹp kích thước $n \times n$.
Dữ liệu vào: một dòng gồm hai số $n$ và $k$ $(2 \le n \le 200,\ 2 \le k \le \min(n, 3))$.
Kết quả: nếu có bảng, 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 ($40\%$ số điểm): $k = 2$.
- Subtask 2 ($60\%$ số điểm): $k = 3$.
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.
4 20 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 code ở dưới in ra cho ví dụ khác bảng của đề nhưng vẫn đúng.
Lời mở đầu
Đây là "phiên bản khó" của bài Bảng số B (bảng B cùng vòng chung kết, chỉ có $k = 2$). Với $k = 2$, chỉ cần đặt 4 góc cho từng vành là xong. Nhưng với $k = 3$ thì mỗi vành chỉ có 4 góc – không đủ chỗ cho 3 số trên mỗi hàng. Mình sẽ tổng quát hoá ý tưởng "bọc vành" thành "ghép khung dày $t$ ô": tìm một bảng nhỏ bằng quay lui, cắt nó làm 4 góc, rồi bọc quanh một bảng nhỏ hơn. Toàn bộ quá trình là một hàm đệ quy rất ngắn.
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 25 test (mình tự sinh theo đúng tỉ lệ subtask), mỗi test là một dòng $n\ k$:
| Nhóm | Test | Các giá trị $n$ | Test in -1 |
|---|---|---|---|
| Subtask 1 (40%) | 1–10 | 4, 2, 3, 5, 15, 64, 123, 198, 199, 200 | không |
| Subtask 2 (60%) | 11–25 | 3, 4, 5, 6, 7, 10, 11, 12, 45, 97, 147, 196, 198, 199, 200 | test 11, test 12 |
- Test 1 là ví dụ của đề. Mỗi subtask đều có $n$ nhỏ nhất có thể và $n$ lớn tới 200.
- Với $k = 3$, có đúng hai giá trị $n$ không có bảng là $n = 3$ và $n = 4$ (test 11, 12 phải in
-1). Mọi trường hợp khác đều có bảng. - Bài có nhiều đáp án đúng, nên CLUE chấm bằng checker: kiểm tra bảng em in ra có đủ các điều kiện không (và kiểm tra em in
-1đúng lúc).
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 ghép khung |
|---|---|---|---|---|
| Subtask 1 (40%) | $k = 2$ | 1–10 | 6/10 test | qua |
| Subtask 2 (60%) | $k = 3$ | 11–25 | 8/15 test | qua |
Lời giải cách 2 (C++) 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ền các ô theo đúng thứ tự xoắn ốc (mảng ord) để điều kiện 3 tự thoả: chỉ cần nhớ số cần đặt tiếp theo $x$ ($1 \to 2 \to \ldots \to k \to 1$, tức là x % k + 1). Với mỗi ô có 2 lựa chọn:
- Đặt số $x$ – nếu hàng và cột của ô chưa có $x$.
- Để trống – nếu sau đó hàng và cột vẫn còn đủ chỗ cho đủ $k$ số:
demR[r] + conR[r] >= k(đã điền + chưa xét), tương tự với cột. Đây là cắt nhánh giúp quay lui chạy nhanh.
Quay lui này là vét cạn đầy đủ (cắt nhánh chỉ bỏ những nhánh chắc chắn sai), nên nếu nó trả về "không có" thì đúng là không có bảng.
Kết quả chạy thật: bản C++ đúng 14/25 test – quá thời gian test 7–10, 19–25 (test đúng chạy lâu nhất 0,374 giây). Bản Python đúng 13/25 test – quá thời gian test 6–10, 19–25 (test đúng chạy lâu nhất 0,067 giây). Quay lui chỉ kịp với các bảng nhỏ (các test qua được có $n \in \{2, 3, 4, 5, 6, 7, 10, 11, 12, 15, 64\}$), và nó cho ta hai thông tin quý: $k = 3$ với $n = 3, 4$ vô nghiệm, còn $5 \le n \le 10$ đều tìm được bảng rất nhanh.
Ý tưởngGhép khung: cắt bảng nhỏ làm 4 góc
Vì sao $k = 3$, $n = 3$ không có bảng? Lúc này không có ô trống nào, dãy số theo xoắn ốc buộc là $1,2,3,1,2,3,1,2,3$: hàng trên là $1, 2, 3$; cột phải đi xuống gặp $1, 2$; hàng dưới đi sang trái gặp $3, 1$; rồi ô $(1, 0)$ là $2$ và ô giữa là $3$. Khi đó cột trái là $1, 2, 1$ – có hai số 1, vô lý. Trường hợp $n = 4$ thì quay lui ở cách 1 đã vét cạn và xác nhận vô nghiệm.
Xây dựng cho $n$ lớn. Đặt $t = 1$ nếu $k = 2$, $t = 3$ nếu $k = 3$. Giả sử đã có:
- một bảng $k$-đẹp $F$ cỡ $2t \times 2t$ (với $k = 3$ là bảng $6 \times 6$ – quay lui tìm được);
- một bảng $k$-đẹp $S$ cỡ $(n - 2t) \times (n - 2t)$ (gọi đệ quy).
Ta dựng bảng $n \times n$: đặt $S$ vào giữa (lệch $t$ hàng, $t$ cột), còn "khung" dày $t$ ô bao quanh thì chỉ có số ở 4 góc $t \times t$, lấy đúng từ 4 góc của $F$ (hàng/cột $i$ của $F$ với $i < t$ giữ nguyên, với $i \ge t$ dời thành $n - 2t + i$). Hai điều kiện vẫn đúng:
- Hàng, cột: mỗi hàng trong khung (ví dụ hàng $0$) chứa đúng các số của hàng tương ứng trong $F$, các ô giữa đều trống → đủ $1..k$ mỗi số một lần. Các hàng ở giữa có phần khung trống nên chỉ phụ thuộc $S$.
- Xoắn ốc: $t$ vành ngoài của bảng lớn được đi theo đúng thứ tự như $t$ vành của $F$ (phép dời chỉ "kéo giãn" khoảng cách, không đổi thứ tự), và $F$ cỡ $2t$ chỉ có đúng $t$ vành – nên đi hết khung ta gặp đúng dãy số của $F$: $1..k$ lặp lại, kết thúc vừa tròn một chu kỳ (mỗi hàng của $F$ có $k$ số, tổng $2t \cdot k$ số chia hết cho $k$). Sau đó đi vào trong giống hệt xoắn ốc của $S$, lại bắt đầu từ $1$.
giai(sz): nếu $sz \le 10$ thì quay lui (cách 1). Ngược lại lấy $F$ = quay lui cỡ $2t$, $S$ = giai(sz − 2t), ghép khung. Với $k = 3$: $n \ge 11$ giảm dần 6 đơn vị sẽ rơi vào $5..10$ – luôn có bảng. Kết luận: $k = 2$ luôn có bảng; $k = 3$ chỉ vô nghiệm khi $n = 3, 4$.Em nhập $n$, $k$ rồi bấm Tiếp để xem bảng $F$ bị cắt 4 góc (4 màu) và bọc từng lớp khung quanh lõi:
Cách 2Quay lui cho bảng nhỏ + ghép khung
- Hàm
quayLui(sz)là cách 1 viết lại thành hàm (đặt lại các mảng mỗi lần gọi), dùng cho $sz \le 10$ và cho bảng $F$ cỡ $2t$. giai(sz)đệ quy với độ sâu khoảng $n / (2t) \le 100$; mỗi tầng tạo bảng $sz^2$ ô nên tổng thời gian cỡ $O(n^3 / t)$ – rất nhỏ với $n \le 200$.- Công thức dời
x = (i < t ? i : sz - 2 * t + i): nửa trên của $F$ ở nguyên chỗ, nửa dưới bị đẩy xuống đáy bảng lớn (tương tự với cột). - Với $k = 3$, $n = 3$ hoặc $4$:
quayLuitrả về bảng rỗng → in-1.
Kết quả chạy thật: bản C++ đúng 25/25 test, chậm nhất 0,010 giây. Bản Python đúng 25/25 test, chậm nhất 0,106 giây.
Nhận xét
Đăng nhận xét