Rối loạn quả cân
Đề bài
Mô tả
Đây là bài toán tương tác.
Ai cũng biết rằng độ lớn chính xác của trọng lực Trái Đất thay đổi theo từng nơi. Alice và Bob sống ở hai quốc gia khác nhau và muốn làm thí nghiệm để kiểm chứng điều này. Đầu tiên, hai người hẹn gặp nhau ở Việt Nam và mỗi người mua một chiếc cân giống hệt nhau. Sau đó họ bay về nước và chuẩn bị một số quả cân, đảm bảo rằng chiếc cân hiển thị đúng 1KG cho mỗi quả cân. Cuối cùng, họ lại bay sang Việt Nam và so sánh các quả cân của mình. Quả nhiên, khi đặt một quả cân của Bob và một quả cân của Alice lên hai đĩa của một chiếc cân đĩa, cân không thăng bằng!
Sau cả ngày làm thí nghiệm, hai người quyết định nghỉ giải lao. Tuy nhiên vì không dọn dẹp, khi quay lại, Alice và Bob không biết quả cân nào là của ai. Họ cũng không nhớ mỗi người đã mang bao nhiêu quả cân, vì có quá nhiều quả cân. Giờ hai người cần dọn dẹp và mang quả cân của mình về nhà. Dưới đây là tóm tắt những gì Alice và Bob biết:
- Có đúng quả cân, đánh số từ đến , bề ngoài không phân biệt được;
- Mỗi người mang ít nhất một quả cân;
- Mọi quả cân của Alice có cùng khối lượng;
- Mọi quả cân của Bob có cùng khối lượng;
- Khối lượng quả cân của Alice khác khối lượng quả cân của Bob;
- Số quả cân của Alice nhỏ hơn hoặc bằng số quả cân của Bob.
Trước tiên, họ muốn biết mỗi người đã mang bao nhiêu quả cân. Để làm vậy, họ dùng chính chiếc cân đĩa đó. Trong một lần cân, họ đặt một số quả cân lên mỗi đĩa của cân và quan sát một trong các kết quả sau:
- Đĩa bên trái nặng hơn;
- Đĩa bên phải nặng hơn;
- Cân thăng bằng.
Hãy giúp hai người tìm số quả cân mà Alice đã mang, dùng không quá lần cân.
Tương tác
Mỗi test gồm nhiều bộ dữ liệu. Đầu tiên chương trình của bạn đọc số bộ dữ liệu (). Với mỗi bộ dữ liệu, chương trình của bạn tương tác với chương trình của ban giám khảo như sau.
Đầu tiên, chương trình của bạn đọc số nguyên (), nghĩa là tổng số quả cân của hai người là .
Sau đó, chương trình của bạn có thể dùng cân như sau:
- Trên dòng đầu tiên, in ra
? cntl cntr(; ): số quả cân đặt lên đĩa trái và đĩa phải; - Trên dòng tiếp theo, in ra số (): chỉ số các quả cân đặt lên đĩa trái;
- Trên dòng tiếp theo, in ra số (): chỉ số các quả cân đặt lên đĩa phải;
- Tất cả số phải đôi một phân biệt;
- Sau đó đọc một ký tự (
>,=,<) là kết quả cân:- Nếu đọc được
>, đĩa trái nặng hơn; - Nếu đọc được
<, đĩa phải nặng hơn; - Nếu đọc được
=, cân thăng bằng.
- Nếu đọc được
Khi đã biết là số quả cân Alice mang, in ra ! k, rồi tiếp tục với bộ dữ liệu kế tiếp, hoặc kết thúc chương trình nếu không còn bộ dữ liệu nào. Lệnh này không được tính vào giới hạn số lần cân.
Đảm bảo tổng qua tất cả các bộ dữ liệu không vượt quá .
Chương trình của ban giám khảo không thích nghi: khối lượng và chủ sở hữu của từng quả cân được xác định trước khi tương tác và không thay đổi trong quá trình tương tác.
Sau mỗi lần in truy vấn, đừng quên xuống dòng và flush đầu ra: cout.flush() hoặc fflush(stdout) trong C++, sys.stdout.flush() trong Python.
Ràng buộc
- , , tổng không vượt quá .
- Mỗi bộ dữ liệu dùng không quá lần cân.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 1 < 2 > > < |
? 1 1 1 2 ! 1 ? 2 2 1 2 3 4 ? 2 2 2 3 1 4 ? 1 1 3 2 ! 1 |
Cột Input là những gì chương trình đọc được, cột Output là những gì chương trình in ra. Bộ thứ nhất: , có quả cân; vì mỗi người mang ít nhất một quả, Alice mang quả (quả số nặng hơn quả số ). Bộ thứ hai: , Alice mang quả số (nặng hơn), Bob mang các quả . Lần cân thứ nhất: nặng hơn ; lần thứ hai: nặng hơn ; lần thứ ba: quả nhẹ hơn quả . Đề gốc minh họa một cách cân khác trên cùng bộ quả cân; ví dụ chỉ minh họa cách trao đổi, không minh họa cách suy ra đáp án. |
| 2 2 < = < 3 < > < < > |
? 2 2 1 2 3 4 ? 2 2 2 3 1 4 ? 1 1 2 3 ! 2 ? 4 4 1 2 3 4 5 6 7 8 ? 4 4 3 4 5 6 1 2 7 8 ? 4 4 2 3 4 5 1 6 7 8 ? 1 1 5 6 ? 1 1 3 4 ! 3 |
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất: , Alice mang quả (nhẹ hơn), Bob mang quả , nên . Bộ thứ hai: , Alice mang các quả (nặng hơn), Bob mang các quả còn lại, nên . |
Bình luận