Thử thách 5 quân xe B (Tin học trẻ toàn quốc 2025 – Vòng chung kết toàn quốc – Bảng B)

Nguồn: Tin học trẻ 2025 – Chung kết toàn quốc – Bảng B Độ khó: Khá Bài tương tác Nguyên lý Dirichlet Chia đôi

Đề bài

Giờ ra chơi, Alice vẽ một bảng $8 \times 8$ ô vuông (hàng đánh số 1..8 từ trên xuống, cột đánh số 1..8 từ trái sang) và bí mật tô đen đúng 33 ô.

Bob phải chỉ ra 5 ô đen sao cho nếu đặt 5 quân xe lên 5 ô đó thì không có hai quân nào ăn nhau – tức là 5 ô nằm trên 5 hàng khác nhau và 5 cột khác nhau.

Bob không được nhìn bảng. Mỗi lần, Bob được chọn một tập ô bất kì và hỏi Alice: "trong các ô này có bao nhiêu ô đen?". Alice luôn trả lời đúng. Giờ ra chơi ngắn nên Bob muốn hỏi càng ít câu càng tốt. Em hãy giúp Bob.

Tương tác:

• Đầu tiên chương trình đọc số nguyên $T$ $(1 \le T \le 100)$ – số bảng bí mật. Sau đó xử lí lần lượt từng bảng.
• Để hỏi tập gồm $k$ ô phân biệt $(r_1, c_1), \ldots, (r_k, c_k)$ $(1 \le k \le 64)$, in một dòng ? k r1 c1 r2 c2 ... rk ck rồi đọc một số nguyên – số ô đen trong tập đó.
• Khi đã tìm được 5 ô đen hợp lệ $(x_1, y_1), \ldots, (x_5, y_5)$, in một dòng ! x1 y1 x2 y2 x3 y3 x4 y4 x5 y5 rồi chuyển sang bảng tiếp theo. Dòng này không tính là câu hỏi.
• Sau mỗi dòng in ra phải xuống dòng và làm sạch bộ đệm: fflush(stdout) hoặc cout.flush() (C++), sys.stdout.flush() (Python). Mỗi bảng không được hỏi quá 64 câu.

Chấm điểm: nếu mọi bảng đều được trả lời đúng, gọi $Q$ là số câu hỏi lớn nhất đã dùng cho một bảng (trong cả $T$ bảng của test). Điểm của test:

• 100% nếu $Q \le 9$;
• $0{,}9 - (Q - 9) \times 0{,}01$ số điểm nếu $9 < Q \le 64$;
• 0 điểm nếu $Q > 64$ (hoặc trả lời sai).

Subtask:

• Subtask 1 (30% số điểm): trong 8 ô của đường chéo chính (số hàng bằng số cột) có đúng 5 ô đen.
• Subtask 2 (70% số điểm): không có ràng buộc gì thêm.

Giới hạn thời gian: 1 giây, bộ nhớ: 512 MB.

Ví dụ – input

1

2

0

3

Ví dụ – output

? 3 1 1 2 2 3 3

? 1 3 3

? 3 4 4 5 5 6 6

! 1 1 2 2 4 4 5 5 6 6

Giải thích: có $T = 1$ bảng. Câu hỏi 1: trong 3 ô $(1,1), (2,2), (3,3)$ có 2 ô đen; câu hỏi 2: ô $(3,3)$ trắng, suy ra $(1,1)$ và $(2,2)$ đen; câu hỏi 3: cả 3 ô $(4,4), (5,5), (6,6)$ đều đen. Năm ô $(1,1),$ $(2,2),$ $(4,4),$ $(5,5),$ $(6,6)$ khác hàng, khác cột. Ở ví dụ này $Q = 3$. Các dòng trống chỉ để dễ nhìn thứ tự hỏi – đáp.

Ghi chú: bài này có hai phiên bản giống hệt nhau, chỉ khác công thức điểm khi $9 < Q \le 64$: bảng B và bảng C2 (xem bài Thử thách 5 quân xe C). Bài này là phiên bản Bảng B.

Nguồn: Hội thi Tin học trẻ toàn quốc 2025 – Vòng chung kết toàn quốc – Bảng B. Đề bài được mình viết lại bằng lời của mình cho dễ hiểu, giữ nguyên ý nghĩa và số liệu.

Lời mở đầu

Đây là một bài tương tác: chương trình không đọc hết dữ liệu ngay từ đầu, mà "nói chuyện" với trình chấm – hỏi một câu, đọc câu trả lời, rồi quyết định hỏi gì tiếp. Điểm phụ thuộc vào số câu hỏi, nên ai cũng làm được "đúng", cái khó là làm ít câu. Lời giải đẹp của bài dựa trên một ý tưởng rất ngắn gọn: chia bảng thành 8 đường chéo vòng và dùng nguyên lý Dirichlet (chuồng bồ câu).

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

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 OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test26 testCách 1chéo chínhCách 2hỏi 64 ôÝ tưởngDirichletCách 3–4≤ 9 câuCách 58 câu

Bộ testBộ test có gì?

Bộ test mình dùng có 26 test: test 1–8 là subtask 1 (đúng 30%), test 9–26 là subtask 2. Mỗi test là $T$ bảng bí mật, mỗi bảng đúng 33 ô đen (mình đã kiểm tra lại từng bảng). Test 1 chính là bảng của ví dụ trong đề.

Nhóm	Test	Số bảng $T$ mỗi test	Tổng số bảng	Số ô đen trên đường chéo chính	Bảng "khó" (đường chéo vòng nhiều nhất chỉ 5 ô đen)
Subtask 1	1–8	1, 20, 50, 100	372	5 – 5	216
Subtask 2	9–26	1, 100	1701	0 – 8	765

• Bộ test có nhiều kiểu bảng "khó chịu": 4 hàng tô kín + 1 ô, 4 cột tô kín + 1 ô, hai khối $4 \times 4$ đối nhau + 1 ô, bàn cờ vua + 1 ô, 4 đường chéo vòng + 1 ô...
• Đặc biệt có các bảng mà mỗi đường chéo vòng có 4 ô đen, riêng một đường có 5 ô (test 12 và 18 toàn bảng như vậy) – trường hợp xấu nhất cho lời giải dựa trên đường chéo vòng bên dưới.

Vì là bài tương tác nên mình chấm bằng chính trình tương tác (interactor) viết theo đề: nó đọc bảng bí mật, trả lời từng câu hỏi, kiểm tra 5 ô cuối cùng và tính điểm theo $Q$. Mình tính điểm subtask = tỉ lệ điểm thấp nhất trong các test của subtask. Lời giải cuối cùng (cách 5) mình đã nộp thử trên hệ thống chấm chính thức của Hội thi (tinhoctre.vn) và được AC (100 điểm). Kết quả chạy thật các cách bên dưới:

Subtask	Test	Cách 1 chéo chính	Cách 2 hỏi 64 ô	Cách 3 chéo vòng + từng ô	Cách 4 chéo vòng + cặp ô	Cách 5 cây quyết định
Subtask 1 (30%)	1–8	Q = 8 100%	Q = 64 35%	Q = 10 89%	Q = 9 100%	Q = 8 100%
Subtask 2 (70%)	9–26	sai 17 test 0%	Q = 64 35%	Q = 10 89%	Q = 9 100%	Q = 8 100%
Tổng điểm		30	35	89	100	100

Tương tácBài tương tác chạy thế nào?

Chương trình của em và trình chấm nối với nhau bằng hai "đường ống": cái em printf ra thì trình chấm đọc được, cái trình chấm in ra thì em scanf được. Vì vậy:

• In xong câu hỏi phải fflush(stdout) ngay, nếu không câu hỏi còn nằm trong bộ đệm, trình chấm chờ em, em chờ trình chấm → treo (thường bị báo quá thời gian).
• Ví dụ trong đề cho thấy luồng hội thoại: phần "input" là những gì trình chấm gửi cho em ($T$ và các câu trả lời), phần "output" là những gì em in ra (các câu hỏi và đáp án).

Về khung chạy tay bên dưới

Khung chạy tay không có trình chấm thật, nên ô "Dữ liệu vào" chứa sẵn những gì trình chấm sẽ gửi: số $T$ rồi lần lượt các câu trả lời (mình lấy bằng cách cho lời giải chạy với một bảng bí mật thật trong bộ test). Chương trình đọc chúng theo đúng thứ tự như khi chạy thật.

Cách 1Subtask 1: hỏi từng ô trên đường chéo chính

Ở subtask 1, đường chéo chính có đúng 5 ô đen, mà các ô $(i, i)$ thì đôi một khác hàng, khác cột. Vậy chỉ cần hỏi lần lượt từng ô $(1,1), (2,2), \ldots$ cho tới khi gặp đủ 5 ô đen: tối đa 8 câu hỏi ≤ 9 → trọn điểm subtask 1.

C++▶ Chạy tay từng dòng codeCách 1: hỏi từng ô (i, i) cho tới khi đủ 5 ô đen. Dữ liệu vào = những gì trình chấm gửi (T rồi các câu trả lời).

Dữ liệu vào (stdin) – sửa thoải mái1 1 1 0 1 1 1

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Kết quả chạy thật: số câu hỏi lớn nhất ở subtask 1 là Q = 8, ở subtask 2 là sai 17/18 test (chỉ ra ô trắng hoặc không đủ 5 ô); điểm: subtask 1 được 100%, subtask 2 được 0% → 30/100 điểm. Thời gian CPU lớn nhất 0,004 giây. Ở subtask 2 đường chéo chính có thể có ít hơn 5 ô đen (có bảng chỉ 0 ô) nên chương trình in thiếu ô → sai.

Cách 2Hỏi cả 64 ô rồi quay lui

Cách "chắc ăn" nhất: hỏi từng ô một (64 câu) để biết toàn bộ bảng, rồi quay lui chọn mỗi hàng một ô đen ở cột chưa dùng (hoặc bỏ qua hàng) cho tới khi đủ 5 quân xe. Luôn tìm được vì có thể chứng minh 33 ô đen luôn chứa 5 ô khác hàng khác cột (xem phần ý tưởng).

C++▶ Chạy tay từng dòng codeCách 2: hỏi cả 64 ô (64 câu) rồi quay lui chọn 5 ô đen khác hàng khác cột.

Dữ liệu vào (stdin) – sửa thoải mái1 1 0 0 1 1 0 1 0 0 1 0 1 1 1 1 0 0 1 0 0 0 1 1 0 1 1 1 1 0 1 1 0 0 1 0 0 1 0 1 1 1 0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 1 1 0 0 1 1 1 0

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Kết quả chạy thật: số câu hỏi lớn nhất ở subtask 1 là Q = 64, ở subtask 2 là Q = 64; điểm: subtask 1 được 35%, subtask 2 được 35% → 35/100 điểm. Thời gian CPU lớn nhất 0,026 giây. Luôn đúng nhưng $Q = 64$ nên mỗi test chỉ được 35% số điểm.

Ý tưởngĐường chéo vòng + nguyên lý Dirichlet

Đánh số hàng, cột từ 0 đến 7. Đường chéo vòng thứ $d$ $(d = 0..7)$ gồm 8 ô $(r,\ (r + d) \bmod 8)$ với $r = 0..7$ – giống đường chéo chính nhưng "dịch phải" $d$ cột, chạm mép phải thì vòng lại mép trái. Hai tính chất:

1. 8 đường chéo vòng chia đôi bảng không trùng lặp: mỗi ô $(r, c)$ thuộc đúng đường $d = (c - r) \bmod 8$.
2. Mỗi đường có đúng một ô trên mỗi hàng và một ô trên mỗi cột. Nên 5 ô đen bất kì trên cùng một đường chéo vòng luôn hợp lệ!

Nguyên lý Dirichlet

33 ô đen chia vào 8 đường chéo vòng. Nếu đường nào cũng có ≤ 4 ô đen thì tổng ≤ 32 < 33 – vô lí. Vậy luôn có một đường chéo vòng chứa ít nhất 5 ô đen. (Đây cũng là lí do 33 ô đen luôn có lời giải.)

Tìm đường đó bằng 3 câu hỏi (chia đôi): giữ một nhóm đường chéo cand và số ô đen total của nhóm, luôn đảm bảo total > 4 × (số đường trong cand). Ban đầu cand = cả 8 đường, total = 33 > 32. Hỏi nửa trái $L$ (một nửa số đường) được $x$ ô đen:

• nếu $x > 4|L|$ thì nửa trái vẫn giữ tính chất → cand = L, total = x;
• ngược lại nửa phải có $total - x > 4|cand| - 4|L|$ $= 4|R|$ → cand = R, total = total − x (không cần hỏi!).

8 → 4 → 2 → 1 đường: sau 3 câu hỏi ta có một đường chéo $D$ với biết chính xác $c \ge 5$ ô đen. Việc còn lại: tìm ra 5 ô đen trong 8 ô của $D$ bằng ít câu hỏi nhất.

Em chọn một bảng (hoặc nhập 64 kí tự 0/1, hoặc một số bất kì để sinh bảng ngẫu nhiên) rồi bấm Tiếp để xem chiến thuật đầy đủ của cách 4. Ô đen của bảng bí mật được vẽ mờ để em theo dõi – Bob thì không nhìn thấy:

Bảng (64 kí tự 0/1 hoặc 1 số):

Ví dụ nhanh:

Cách 3Chia đôi đường chéo + hỏi từng ô

Sau 3 câu tìm được đường $D$ có $c$ ô đen, hỏi lần lượt từng ô của $D$. Dừng khi đã gặp đủ 5 ô đen; còn nếu đã gặp đủ $8 - c$ ô trắng thì các ô còn lại chắc chắn đen, không cần hỏi. Trường hợp xấu nhất $c = 5$: phải hỏi 7 ô → tổng $3 + 7 = 10$ câu.

C++▶ Chạy tay từng dòng codeCách 3: 3 câu chia đôi tìm đường chéo vòng có ≥ 5 ô đen, rồi hỏi từng ô.

Dữ liệu vào (stdin) – sửa thoải mái1 17 6 4 1 1 1 1 1

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. askDiag(ds) gom tất cả ô của các đường chéo trong ds vào một câu hỏi (mỗi đường 8 ô).
2. Hàm ask in câu hỏi, fflush, đọc câu trả lời; nếu đọc được số âm (trình chấm báo lỗi) thì thoát ngay.

Kết quả chạy thật: số câu hỏi lớn nhất ở subtask 1 là Q = 10, ở subtask 2 là Q = 10; điểm: subtask 1 được 89%, subtask 2 được 89% → 89/100 điểm. Thời gian CPU lớn nhất 0,008 giây. Chỉ hơn ngưỡng 9 đúng 1 câu nhưng mất điểm ở mọi test có bảng "xấu".

Cách 4Hỏi theo cặp ô – đủ 9 câu

Chia 8 ô của $D$ thành 4 cặp (hàng 0–1, 2–3, 4–5, 6–7). Hỏi 3 cặp đầu, cặp thứ 4 suy ra từ $c$. Cặp có 2 ô đen → lấy cả hai; cặp có 1 ô đen → hỏi thêm ô đầu là biết ô nào đen. Đếm số câu trong trường hợp xấu nhất:

• $c = 5$: số đen của 4 cặp là $\{2, 1, 1, 1\}$ (hoặc $\{2, 2, 1, 0\}$ – chỉ cần thêm 1 câu). Xấu nhất phải hỏi thêm 3 cặp có 1 ô đen → 3 + 3 = 6 câu.
• $c = 6$: $\{2, 2, 1, 1\}$ hoặc $\{2, 2, 2, 0\}$ – thêm tối đa 1 câu. $c \ge 7$: đã có ≥ 3 cặp đủ 2 ô → không hỏi thêm.

Tổng tối đa $3 + 3 + 3 = 9$ câu → 100% số điểm.

C++▶ Chạy tay từng dòng codeCách 4: chia đôi tìm đường chéo, rồi hỏi theo cặp ô – tối đa 9 câu.

Dữ liệu vào (stdin) – sửa thoải mái1 17 6 4 2 2 2

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Kết quả chạy thật: số câu hỏi lớn nhất ở subtask 1 là Q = 9, ở subtask 2 là Q = 9; điểm: subtask 1 được 100%, subtask 2 được 100% → 100/100 điểm. Thời gian CPU lớn nhất 0,006 giây.

Cách 5Nâng cao: cây quyết định tối ưu – 8 câu

Cách 4 đã đủ điểm tối đa, nhưng câu hỏi trên đường $D$ có thể là tập ô bất kì, không chỉ cặp. Lời giải mình nộp chính thức dùng máy tính tự tìm chiến thuật tối ưu: gọi các cấu hình là các cách tô $c$ ô đen trong 8 ô ($\binom{8}{c}$ cách, tối đa 56 – biểu diễn bằng mask 8 bit). Trạng thái là tập cấu hình còn khả dĩ (bitmask tối đa 56 bit).

• Đã "xong" nếu giao của mọi cấu hình còn lại có ≥ 5 ô (5 ô đó chắc chắn đen).
• solve(st, d): thử mọi câu hỏi q (tập con 8 ô), chia các cấu hình theo câu trả lời popcount(cfg & q); câu hỏi tốt nếu mọi nhóm đều giải được với $d - 1$ câu (minimax). Có nhớ theo (st, d).

Tìm kiếm vét cạn cho kết quả: $c = 5$ cần 5 câu, $c = 6$ cần 4, $c = 7$ cần 2, $c = 8$ không cần câu nào → tổng tối đa $3 + 5 = 8$ câu.

C++▶ Chạy tay từng dòng codeCách 5: cây quyết định tối ưu tìm bằng minimax (lời giải đã nộp chính thức). Bước gọi solve() lần đầu có thể mất khoảng 1 giây để tìm kiếm.

Dữ liệu vào (stdin) – sửa thoải mái1 17 6 4 2 3

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Hàm solve() (tìm kiếm minimax) được tính gộp trong một bước ở dòng gọi nó.

Kết quả chạy thật: số câu hỏi lớn nhất ở subtask 1 là Q = 8, ở subtask 2 là Q = 8; điểm: subtask 1 được 100%, subtask 2 được 100% → 100/100 điểm. Thời gian CPU lớn nhất 0,123 giây (thời gian chủ yếu là lần tìm kiếm minimax đầu tiên; các bảng sau dùng lại bảng nhớ).

Tổng kếtKết quả chạy thật trên bộ test

Cách	Q lớn nhất	Số test sai	Điểm subtask 1	Điểm subtask 2	Tổng
1. Chéo chính	8	17	100%	0%	30
2. Hỏi 64 ô	64	0	35%	35%	35
3. Chéo vòng + từng ô	10	0	89%	89%	89
4. Chéo vòng + cặp ô	9	0	100%	100%	100
5. Cây quyết định	8	0	100%	100%	100

Ghi chú của mình: mọi kết quả trên đều chấm bằng trình tương tác thật trên 26 test của mình (phiên bản Bảng B). Cách 1 chỉ đủ 30%; hỏi cả 64 ô luôn đúng nhưng điểm thấp; ý tưởng đường chéo vòng + Dirichlet + chia đôi đưa số câu xuống 10 (cách 3), hỏi theo cặp còn 9 (cách 4, đủ 100%), và cây quyết định tối ưu còn 8 (cách 5, đã AC trên hệ thống chấm chính thức). Bài này mình không viết bản Python vì phần chính là chiến thuật hỏi; nếu viết Python nhớ print(..., flush=True).

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇