Đổ nước (Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 3 – Bảng B)
Đề 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.
1 2 32
3 1
2 3Giả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é.
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 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:
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$):
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.
- 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ủaunordered_map. Bảngtracevừ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 |
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).
- Mảng
idlưu số hiệu bình (1, 2, 3), sắp xếp theov[]– 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ậtv[i]trước khiv[j]đổi). - Lượng nước tối đa là tổng ban đầu ($\le 3 \cdot 10^6$), dùng
long longcho chắc.
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) |