Lập Trình Thuật Toán

Nguồn: Hội thi Tin học trẻ toàn quốc 2025 – Vòng khu vực miền Bắc & miền Trung – Bảng B Độ khó: Trung bình BFS Xây dựng

Đề bài

Có 5 hộp bi đánh số từ 1 đến 5, lúc đầu hộp thứ $i$ có $a_i$ viên bi. Người chơi muốn dồn toàn bộ bi về chung một hộp, và mỗi bước chỉ được làm như sau:

chọn ba hộp khác nhau $i, j, k$, trong đó hộp $i$ và hộp $j$ đều còn bi;
lấy 1 viên ở hộp $i$ và 1 viên ở hộp $j$, bỏ cả hai viên vào hộp $k$.

Như vậy sau một bước: $a_i$ giảm 1, $a_j$ giảm 1, $a_k$ tăng 2, hai hộp còn lại giữ nguyên.

Yêu cầu: cho $a_1, a_2, \dots, a_5$, hãy chỉ ra một cách dồn hết bi về một hộp với không quá $10^6$ bước (không cần ít bước nhất).

Dữ liệu vào: một dòng gồm 5 số nguyên không âm $a_1, a_2, a_3, a_4, a_5$. Dữ liệu đảm bảo luôn có cách dồn.

Kết quả: dòng đầu là số bước $s$; $s$ dòng sau, mỗi dòng ba số $i\ j\ k$ mô tả một bước (lấy bi từ hai hộp $i, j$ bỏ sang hộp $k$). Có nhiều cách thì in cách nào cũng được.

Subtask (gọi $S = a_1 + a_2 + \dots + a_5$ là tổng số bi):

Subtask 1 (40%): $S \le 10$.
Subtask 2 (30%): $S \le 100$.
Subtask 3 (30%): $S \le 10^5$.

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.

Ví dụ – input

2 1 2 1 0

Ví dụ – output

Giải thích: số bi trong 5 hộp sau từng bước: $(2,1,2,1,0) \to (1,1,1,1,2) \to (0,1,0,1,4) \to (0,0,0,0,6)$. Đây chỉ là một đáp án; bài có trình chấm riêng nên cách nào hợp lệ cũng được chấp nhận – ví dụ lời giải Cách 1 bên dưới chỉ cần 2 bước: 1 2 3 cho $(1,0,4,1,0)$ rồi 1 4 3 cho $(0,0,6,0,0)$.

Lời mở đầu

Đây là bài "xây dựng" (constructive) dễ thương của bảng B: đề không bắt tìm số bước ít nhất, chỉ cần chỉ ra được một cách. Với số bi nhỏ, ta có thể để máy tự tìm bằng BFS trên không gian trạng thái. Nhưng khi tổng số bi lên tới $10^5$ thì phải tìm ra một "chiêu" chuyển bi thật gọn – và chiêu đó chỉ gồm 3 bước. Mình sẽ đi lần lượt từ BFS tới chiêu 3 bước nhé.

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ộ test20 test Ý tưởngchiêu 3 bước Cách 1BFS toàn bộ Cách 2full Tổng kếtkết quả

Bộ testBộ test có gì?

Bộ test của mình có 20 test (giống bộ trên CLUE), chia đúng theo 3 subtask của đề: test 1–8 có $S \le 10$, test 9–14 có $S \le 100$, test 15–20 có $S$ tới $10^5$. Vì có nhiều đáp án đúng nên bài được chấm bằng trình chấm (checker): nó mô phỏng lại từng bước của em, kiểm tra 3 hộp khác nhau, hai hộp $i, j$ còn bi, số bước $\le 10^6$ và cuối cùng chỉ còn tối đa một hộp có bi.

Nhóm	Test	Tổng số bi $S$	Hộp nhiều bi nhất	Test đặc biệt	Số bước Cách 2 in ra (ít nhất – nhiều nhất)
Subtask 1	1–8	0 – 10	9	test 2: cả 5 hộp rỗng test 3: đã dồn sẵn test 4: gần như dồn sẵn test 5: gần như dồn sẵn test 6: gần như dồn sẵn test 8: gần như dồn sẵn	0 – 5
Subtask 2	9–14	97 – 100	99	test 10: gần như dồn sẵn	5 – 76
Subtask 3	15–20	99.998 – 100.000	99.999	test 16: gần như dồn sẵn	5 – 79.996

Có các test "bẫy" nhỏ: cả 5 hộp đều rỗng (in 0) và bi đã nằm sẵn trong một hộp (cũng in 0). Code phải kiểm tra điều kiện kết thúc trước khi làm bất cứ bước nào.
Cột cuối là số bước mà lời giải Cách 2 in ra: lớn nhất cũng chỉ khoảng $8 \cdot 10^4$, còn rất xa giới hạn $10^6$.

Kết quả chạy thật của 2 cách bên dưới theo từng subtask:

Subtask	Điều kiện	Test	Cách 1 BFS toàn bộ	Cách 2 3 bước + BFS nhỏ
Subtask 1 (40%)	$S \le 10$	1–8	qua	qua
Subtask 2 (30%)	$S \le 100$	9–14	1/6 test	qua
Subtask 3 (30%)	$S \le 10^5$	15–20	2/6 test	qua

Lời giải theo đúng ý tưởng Cách 2 (chỉ khác là khi $S \le 30$ thì BFS toàn bộ như Cách 1) mình đã nộp thử trên trang chấm chính thức tinhoctre.vn và đạt 100 điểm (AC).

Ý tưởngTrạng thái, BFS và chiêu "3 bước chuyển 3 viên"

Trạng thái của trò chơi là bộ 5 số $(a_1, \dots, a_5)$. Mỗi bước biến trạng thái này thành trạng thái khác, nên ta có thể coi mỗi trạng thái là một đỉnh, mỗi bước là một cạnh – bài toán trở thành tìm đường đi từ trạng thái ban đầu tới một trạng thái "chỉ còn 1 hộp có bi". Đó chính là việc của BFS (tìm kiếm theo chiều rộng). Từ một trạng thái có tối đa $\binom{5}{2} \cdot 3 = 30$ bước đi (chọn cặp $i < j$ rồi chọn $k$ trong 3 hộp còn lại).

Vấn đề là số trạng thái bằng số cách chia $S$ viên vào 5 hộp: $\binom{S+4}{4}$. Với $S = 10$ chỉ có $1001$ trạng thái, nhưng $S = 100$ đã là khoảng $4{,}6$ triệu, còn $S = 10^5$ thì khỏi nghĩ. Ta cần một cách "đi thẳng" về đích.

Chiêu 3 bước: chuyển đúng 3 viên từ hộp $x$ sang hộp $t$

Chọn thêm một hộp trung gian $y$ (khác $x$ và $t$), rồi làm 3 bước:

Bước	$(i, j \to k)$	hộp $x$	hộp $t$	hộp $y$
1	$(x, t \to y)$	$-1$	$-1$	$+2$
2	$(x, y \to t)$	$-1$	$+2$	$-1$
3	$(x, y \to t)$	$-1$	$+2$	$-1$
Tổng cộng		$-3$	$+3$	$0$

Hộp $y$ cho "mượn" 2 viên rồi nhận lại đủ, nên số bi của nó không đổi. Điều kiện: hộp $x$ có ít nhất 3 viên và hộp $t$ có ít nhất 1 viên (để làm được bước 1; sau bước 1 thì $y$ chắc chắn có $\ge 2$ viên).

Từ đó có thuật toán:

Chọn $t$ là hộp nhiều bi nhất.
Với mỗi hộp $x \ne t$: còn $a_x \ge 3$ thì dùng chiêu 3 bước chuyển 3 viên sang $t$. Xong bước này, mọi hộp khác $t$ chỉ còn $0$, $1$ hoặc $2$ viên.
Phần "lẻ" còn lại rất nhỏ: dùng BFS, nhưng chỉ đi qua các trạng thái mà mọi hộp khác $t$ có không quá 6 viên – không gian trạng thái chỉ còn vài nghìn đỉnh. Mình đã kiểm tra bằng máy: BFS này luôn xong trong không quá 5 bước.

Em nhập số bi 5 hộp (tổng không quá 60 cho dễ nhìn) rồi bấm Tiếp để xem thuật toán dồn bi từng bước – hai hộp bị lấy bi tô đỏ, hộp nhận bi tô xanh:

Số bi 5 hộp

Ví dụ nhanh:

Cách 1BFS trên toàn bộ không gian trạng thái (subtask 1)

Ta cài BFS đúng như mô tả ở trên:

Mỗi trạng thái là một array<int, 5>; map par lưu "trạng thái cha" (đồng thời đánh dấu đã thăm), map how lưu bước $(i, j, k)$ đã đi tới trạng thái đó.
Lấy trạng thái $u$ ở đầu hàng đợi: nếu $u$ đã là trạng thái đích (tối đa một hộp có bi) thì dừng. Nếu chưa, thử cả 30 bước đi, trạng thái mới nào chưa thăm thì ghi cha và cho vào hàng đợi.
Cuối cùng đi ngược từ đích về trạng thái ban đầu theo par để lấy dãy bước, đảo ngược lại rồi in.

Vì BFS duyệt theo "tầng" nên đường đi tìm được là ngắn nhất – ví dụ test đề chỉ cần 2 bước. Trường hợp ban đầu đã là đích (kể cả 5 hộp rỗng) thì vòng lặp dừng ngay ở lần lấy đầu tiên và in 0.

C++▶ Chạy tay từng dòng codeCách 1: BFS trên mọi trạng thái (a1..a5), truy vết bằng map par/how.

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

Dữ liệu mẫu:

Hai lần lấy đầu tiên khỏi hàng đợi được chạy chi tiết từng bước đi; các lần sau khung chạy tay tua nhanh 3 vòng for (chỉ báo số trạng thái mới).

Hàm done đếm số hộp còn bi: $\le 1$ là xong.
Vòng for j = i + 1 bảo đảm mỗi cặp $\{i, j\}$ chỉ xét một lần (bước $(i, j \to k)$ và $(j, i \to k)$ là như nhau).
par[a] = a đánh dấu trạng thái ban đầu đã thăm; vòng truy vết dừng khi gặp lại a.

Không gian$O\left(\binom{S+4}{4}\right)$ trạng thái

Thời gian$O\left(30 \cdot \binom{S+4}{4} \cdot \log\right)$

Kết quả chạy thật: bản C++ đúng 11/20 test, quá thời gian test 9, 11–15, 17–19; các test đúng chạy lâu nhất 0,011 giây. Bản Python đúng 11/20 test, quá thời gian test 9, 11–15, 17–19; các test đúng chạy lâu nhất 0,065 giây.

Toàn bộ subtask 1 đúng và chạy tức thì. Ở các test lớn, BFS phải duyệt gần hết hàng triệu trạng thái nên quá thời gian; chỉ vài test "ăn may" (test 10, 16, 20) đúng được vì trạng thái ban đầu đã ở rất gần đích (một hộp chứa gần hết bi).

Cách 2Chiêu 3 bước + BFS nhỏ để hoàn tất (full)

Cài đặt đúng 3 ý ở phần ý tưởng. Hàm mv(i, j, k) vừa cập nhật mảng a vừa ghi bước vào ans, nên phần BFS ở cuối cũng chỉ cần gọi mv theo đường đi tìm được.

C++▶ Chạy tay từng dòng codeCách 2: chiêu 3 bước chuyển 3 viên sang hộp nhiều bi nhất, rồi BFS nhỏ cho phần lẻ.

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

Dữ liệu mẫu:

Phần BFS bên trong hàm bfs được tua nhanh (giống hệt Cách 1) – khung chạy tay chỉ dừng ở các lệnh mv thực hiện đường đi tìm được.

max_element trả về hộp nhiều bi nhất $t$. Nếu có hộp $x \ne t$ còn $\ge 3$ viên thì $a_t \ge a_x \ge 3$, nên bước đầu của chiêu $(x, t \to y)$ luôn hợp lệ, và $a_t$ chỉ tăng dần.
Hộp trung gian $y$ chọn là hộp kế tiếp $x$ (bỏ qua $t$) – hộp nào cũng được, kể cả hộp rỗng.
Trong BFS, dòng if (k != t && v[k] > 6) continue; giới hạn không gian trạng thái; hộp $t$ được phép nhiều bi tuỳ ý.

Vì sao chắc chắn đúng?

Giai đoạn 1 mỗi lần bỏ đi 3 viên khỏi một hộp $x \ne t$ bằng 3 bước, nên tổng số bước $\le S \le 10^5$.
Sau giai đoạn 1, mọi hộp khác $t$ có $\le 2$ viên. Mình cho máy thử mọi trạng thái kiểu này (4 hộp khác $t$ có 0/1/2 viên, hộp $t$ có từ 0 đến 300 viên – khi $a_t$ lớn hơn nữa thì BFS chạy y hệt vì nó chỉ dùng vài bước): BFS luôn tìm được đích trong $\le 5$ bước, trừ đúng các hoán vị của $(2, 1, 0, 0, 0)$.
$(2, 1, 0, 0, 0)$ là trạng thái vô nghiệm: chỉ có 3 viên bi, mỗi bước bắt buộc lấy từ 2 hộp đang có bi bỏ sang hộp thứ ba, kết quả lại là một hộp 2 viên và một hộp 1 viên – không bao giờ dồn được. Đề đảm bảo có lời giải nên không có test này; còn nếu đã chạy giai đoạn 1 thì $a_t \ge 6$ nên cũng không thể rơi vào nó.
Mình còn chạy Cách 2 cho tất cả 80.730 trạng thái có $S \le 22$: chỉ đúng 20 hoán vị của $(2,1,0,0,0)$ là không dồn được, mọi trạng thái còn lại đều thành công.

Không gian$O(S)$ (lưu các bước)

Thời gian$O(S)$ + BFS nhỏ (hằng số)

Kết quả chạy thật: bản C++ đúng 20/20 test; các test đúng chạy lâu nhất 0,020 giây. Bản Python đúng 20/20 test; các test đúng chạy lâu nhất 0,103 giây. Full điểm ở cả hai ngôn ngữ.

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

Cách	Ngôn ngữ	Đúng	Lâu nhất (test đúng)	Ghi chú
1. BFS toàn bộ trạng thái	C++	11/20	0,011s	Quá thời gian test 9, 11–15, 17–19 (cả subtask 2 và 3)
	Python	11/20	0,065s	Quá thời gian test 9, 11–15, 17–19
2. 3 bước chuyển 3 viên + BFS nhỏ	C++	20/20	0,020s	Full điểm
	Python	20/20	0,103s	Full điểm

Ghi chú của mình: thời gian là thời gian CPU đo trên máy mình (giới hạn 1 giây), đáp án được kiểm tra bằng trình chấm mô phỏng lại từng bước. BFS (Cách 1) là công cụ rất mạnh khi không gian trạng thái nhỏ, và ở Cách 2 nó vẫn được dùng để "dọn" phần lẻ cuối cùng. Bài học của bài: khi không gian trạng thái quá lớn, hãy tìm một dãy bước ngắn có tác dụng gọn (ở đây là 3 bước chuyển đúng 3 viên mà hộp trung gian không đổi), rồi lặp lại nó.

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 😇

Lập Trình Thuật Toán

Chuyển bi (Tin học trẻ toàn quốc 2025 – Vòng khu vực miền Bắc & miền Trung – Bảng B)