Đổ nước (Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 3 – Bảng B)

Nguồn: Tin học trẻ toàn quốc 2025 Độ khó: Khá Kiến tạo Biểu diễn nhị phân

Đề bài

Có ba bình nước đánh số 1, 2, 3; mỗi bình chứa được tối đa $V$ lít. Lúc đầu bình 1 có $v_1$ lít, bình 2 có $v_2$ lít, bình 3 có $v_3$ lít nước, với $v_1 + v_2 + v_3 < V$ (nên không bao giờ có bình bị tràn).

Người ta cần lấy ra một bình để dùng việc khác, nên phải đổ nước qua lại giữa các bình sao cho có một bình trở nên rỗng. Mỗi lượt được chọn hai bình $i \ne j$ thoả mãn $v_i \ge v_j$, rồi đổ từ bình $i$ sang bình $j$ đúng $v_j$ lít – tức là lượng nước trong bình $j$ tăng gấp đôi, còn bình $i$ giảm đi đúng lượng đó.

Yêu cầu: đưa ra một dãy các lượt đổ để cuối cùng có ít nhất một bình rỗng.

Dữ liệu vào: một dòng gồm ba số nguyên dương $v_1, v_2, v_3$.

Kết quả:

Dòng đầu ghi số nguyên dương $k$ – số lượt đổ.
$k$ dòng tiếp theo, mỗi dòng ghi hai số $i, j$: lượt đó đổ từ bình $i$ sang bình $j$.

Nếu có nhiều cách, in ra cách bất kỳ (không yêu cầu $k$ nhỏ nhất).

Subtask:

Subtask 1 (20% số điểm): $v_1, v_2, v_3 \le 100$.
Subtask 2 (20% số điểm): $v_1, v_2, v_3 \le 2000$.
Subtask 3 (60% số điểm): $v_1, v_2, v_3 \le 10^6$.

Giới hạn thời gian: 1 giây. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ – input

1 2 3

Ví dụ – output

2
3 1
2 3

Giải thích: ban đầu $(v_1, v_2, v_3) = (1, 2, 3)$. Đổ từ bình 3 sang bình 1 được $(2, 2, 2)$; sau đó đổ từ bình 2 sang bình 3 được $(2, 0, 4)$ – bình 2 đã rỗng.

Lưu ý: bài có nhiều đáp án đúng, trình chấm sẽ mô phỏng các lượt đổ của em để kiểm tra (mỗi lượt phải có $i \ne j$, $v_i \ge v_j$, và cuối cùng có bình rỗng). Đáp án in ra không cần giống ví dụ. Số $V$ không có trong dữ liệu vào và không ảnh hưởng gì tới bài.

Nguồn: Hội thi Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 3 – Bảng B (bài POUR). Đề được mình viết lại cho dễ đọc, giữ nguyên ý và số liệu.

Lời mở đầu

Đây là một bài kiến tạo rất đẹp (ý tưởng rất giống các bài toán Olympic Toán về "ba hộp bi"): đề không hỏi số, mà bắt ta tự xây dựng một dãy thao tác. Với dữ liệu nhỏ ta có thể để máy tự tìm bằng BFS; còn với $v \le 10^6$ thì cần một nhận xét toán học: viết thương ⌊b/a⌋ dưới dạng nhị phân. Mình đi lần lượt từng cách 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ưởngnhị phân Cách 1BFS Cách 2full Tổng kếtkết quả

Bộ testBộ test có gì?

Bộ test của mình gồm 20 test, chia theo đúng tỉ lệ subtask: test 1–4 (subtask 1), 5–8 (subtask 2), 9–20 (subtask 3). Test 1 là ví dụ của đề (file đáp án mẫu là đáp án của lời giải mình, khác ví dụ nhưng đều đúng). Vì nhiều đáp án nên bộ test chấm bằng checker mô phỏng lại các lượt đổ. Lời giải cách 2 đã được nộp thử trên hệ thống chấm chính thức tinhoctre.vn và đạt 100/100 điểm.

Nhóm	Test	$v$ nhỏ nhất – lớn nhất	$k$ của cách 2 (lớn nhất)	$k$ ngắn nhất (BFS) lớn nhất
Subtask 1	1–4	1 – 100	29	7
Subtask 2	5–8	1 – 2.000	66	9
Subtask 3	9–20	1 – 1.000.000	218	12

Có các test đặc biệt: ba bình bằng nhau (1 lượt là xong), $(1, 1, 10^6)$, $(10^6, 10^6 - 1, 10^6 - 2)$, ba số Fibonacci liên tiếp $(832040, 514229, 317811)$, lũy thừa của 2, ba số nguyên tố lớn...
Cột cuối là số lượt ít nhất (BFS tìm được, chỉ với các test BFS chạy kịp). Cách 2 không tối ưu số lượt nhưng đề không yêu cầu; nó dùng nhiều nhất 218 lượt trên bộ test.

Kết quả chạy thật (chấm bằng checker) của các cách theo từng subtask:

Subtask	Điều kiện	Test	Cách 1 BFS C++	Cách 1 BFS Python	Cách 2 C++	Cách 2 Python
Subtask 1 (20%)	$v_i \le 100$	1–4	4/4	4/4	4/4	4/4
Subtask 2 (20%)	$v_i \le 2000$	5–8	4/4	4/4	4/4	4/4
Subtask 3 (60%)	$v_i \le 10^6$	9–20	5/12	5/12	12/12	12/12

Ý tưởngLàm bình nhỏ nhất nhỏ đi bằng phép chia lấy dư

Sắp xếp lại để lượng nước $A \le B \le C$ (ở các bình $a$, $b$, $c$). Nhận xét quan trọng: mọi lượt đổ vào bình $a$ đều làm $a$ gấp đôi: $A \to 2A \to 4A \to 8A \to \ldots$ Như vậy nếu đổ vào $a$ liên tiếp $L$ lần, lượng nước đổ ra ở lượt thứ $t$ ($t = 0, 1, \ldots, L-1$) là đúng $A \cdot 2^t$.

Ta muốn rút từ bình $b$ tổng cộng đúng $A \cdot q$ lít, với $q = \lfloor B / A \rfloor$ – khi đó bình $b$ chỉ còn $B \bmod A < A$, tức là giá trị nhỏ nhất giảm hẳn. Mà $q$ viết được dưới dạng nhị phân: $q = \sum 2^t$ (với các bit $t$ bằng 1). Vậy:

Một vòng của thuật toán

Duyệt các bit của $q$ từ thấp lên cao. Ở bit thứ $t$: nếu bit bằng 1 thì đổ từ $b$ sang $a$, nếu bit bằng 0 thì đổ từ $c$ sang $a$. Sau vòng này, bình $b$ còn đúng $B \bmod A$. Lặp lại (sắp xếp lại, làm vòng mới) cho tới khi có bình rỗng.

Tại sao các lượt đổ luôn hợp lệ?

Lấy từ $b$ ở bit $t$ (bit này bằng 1): trước đó $b$ đã mất $A \cdot (q \bmod 2^t)$, nên còn $B - A(q \bmod 2^t)$ $\ge A \cdot q - A(q \bmod 2^t)$ $\ge A \cdot 2^t$ = lượng nước của $a$ lúc đó ✔.
Lấy từ $c$ ở bit $t$ (bit bằng 0, và $t$ nhỏ hơn bit cao nhất $L - 1$ vì bit cao nhất luôn là 1): tổng $c$ đã đưa ra cộng lượt này không quá $A(2^{t+1} - 1) < A \cdot 2^{L-1}$ $\le A \cdot q$ $\le B$ $\le C$ ✔.

Tại sao thuật toán dừng? Mỗi vòng, giá trị nhỏ nhất trong ba bình giảm thực sự (bình $b$ còn $B \bmod A < A$), mà nó là số nguyên không âm nên sau hữu hạn vòng phải về 0. Trên thực tế số vòng rất ít (giống thuật toán Euclid), mỗi vòng $\le 20$ lượt.

Em nhập ba số rồi bấm Tiếp để xem từng lượt đổ (thanh nước cao thấp, các bit của $q$):

v1 v2 v3 =

Ví dụ nhanh:

Cách 1BFS trên trạng thái (subtask 1, 2)

Coi mỗi bộ $(v_1, v_2, v_3)$ là một đỉnh của đồ thị, mỗi lượt đổ hợp lệ là một cạnh. Tổng $S = v_1 + v_2 + v_3$ không đổi nên chỉ cần lưu $(v_1, v_2)$, số trạng thái không quá $(S + 1)^2$. BFS từ trạng thái đầu cho tới khi gặp trạng thái có bình rỗng, rồi truy vết ngược để in ra dãy lượt đổ – được luôn dãy ngắn nhất.

C++▶ Chạy tay từng dòng codeCách 1: BFS trên các trạng thái (v1, v2, v3), truy vết ra dãy lượt đổ ngắn nhất.

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

Dữ liệu mẫu:

Mỗi trạng thái được mã hoá thành một số enc(v1, v2) = v1·(S+1) + v2 để làm khoá của unordered_map. Bảng trace vừa đánh dấu đã thăm, vừa lưu trạng thái cha và lượt đổ (mã hoá i·3 + j) để truy vết.
Không cần kiểm tra "không tìm thấy" vì bài toán luôn có lời giải (chứng minh ở phần ý tưởng).

Một vài test nhỏ, so sánh số lượt ít nhất (BFS) và số lượt của cách 2:

Test	$v_1\ v_2\ v_3$	BFS (ít nhất)	Cách 2
1	1 2 3	2	2
3	100 99 97	7	7
4	55 46 78	3	29
7	1480 1501 1730	9	66
8	1024 1536 2000	3	23
13	832040 514229 317811	2	36

Không gian$O(S^2)$ trạng thái

Thời gian$O(S^2)$, $S = v_1 + v_2 + v_3$

Kết quả chạy thật: Bản C++ đúng 13/20 test, quá thời gian test 12, 14–18, 20, chạy lâu nhất 3.972s. Bản Python đúng 13/20 test, quá thời gian test 12, 14–18, 20, chạy lâu nhất 4.024s. BFS ăn trọn subtask 1, 2 và cả vài test lớn "may mắn" (ví dụ ba bình bằng nhau, hoặc có bình bằng 1), nhưng với ba số lớn ngẫu nhiên thì số trạng thái lên tới hàng triệu – vượt thời gian.

Cách 2Nhị phân của ⌊b/a⌋ (full điểm)

Cài đặt đúng thuật toán ở phần ý tưởng: mỗi vòng sắp xếp ba chỉ số bình theo lượng nước, tính $q = \lfloor v_b / v_a \rfloor$, rồi duyệt các bit của $q$ (dùng q & 1 và q >>= 1).

C++▶ Chạy tay từng dòng codeCách 2: mỗi vòng duyệt các bit của q = v[b] / v[a]; bit 1 lấy nước từ b, bit 0 lấy từ c.

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

Dữ liệu mẫu:

Mảng id lưu số hiệu bình (1, 2, 3), sắp xếp theo v[] – nhờ vậy khi in ra ta in đúng số hiệu gốc của bình.
Hàm pour(i, j) thực hiện đúng luật: bình $j$ gấp đôi, bình $i$ mất $v_j$ (cập nhật v[i] trước khi v[j] đổi).
Lượng nước tối đa là tổng ban đầu ($\le 3 \cdot 10^6$), dùng long long cho chắc.

Không gian$O(k)$

Thời gian$O(k)$, $k$ = số lượt (vài trăm)

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.004s – full điểm. Bản Python đúng 20/20 test, chạy lâu nhất 0.026s.

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

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
1. BFS trên trạng thái	C++	13/20	3.972s	40 điểm (theo subtask)
1. BFS trên trạng thái	Python	13/20	4.024s	40 điểm (theo subtask)
2. Nhị phân của ⌊b/a⌋	C++	20/20	0.004s	100 điểm (theo subtask)
2. Nhị phân của ⌊b/a⌋	Python	20/20	0.026s	100 điểm (theo subtask)

Ghi chú của mình: chấm bằng checker (mô phỏng các lượt đổ), thời gian là thời gian CPU trên máy mình, giới hạn 1 giây; điểm tính theo subtask. BFS là "vũ khí vạn năng" cho bài kiến tạo với dữ liệu nhỏ – vừa lấy điểm, vừa giúp kiểm tra lời giải chính. Còn ý tưởng full là một mẹo kinh điển: muốn rút đúng $q$ lần lượng $A$ trong khi $A$ cứ gấp đôi, hãy viết $q$ ở hệ nhị phân. Lời giải cách 2 đã đạt 100/100 trên tinhoctre.vn.

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