Cỗ máy kiếm tiền bí ẩn của MofK
Đề bài
Mô tả
Đây là một bài toán tương tác.
MofK đã phát minh ra một máy trò chơi điện tử. Bên trong máy của MofK có đồng xu bí mật. Trạng thái của các đồng xu được biểu diễn bởi một xâu nhị phân độ dài , trong đó nghĩa là đồng xu thứ ngửa mặt sấp, còn nghĩa là đồng xu thứ ngửa mặt ngửa. Vì đây là dãy đồng xu bí mật, không ai ngoài MofK biết xâu trông như thế nào.
Người chơi có thể tương tác với máy bằng cách bỏ đồng xu vào máy, và nếu người chơi đoán đúng trạng thái của dãy đồng xu bí mật bên trong, máy sẽ thưởng cho người chơi toàn bộ số đồng xu bên trong máy, kể cả đồng xu bí mật. Mỗi lần tương tác với máy gồm các bước sau:
- Đầu tiên, người chơi bỏ đồng xu vào máy. Trạng thái của các đồng xu được bỏ vào được biểu diễn bởi một xâu nhị phân , trong đó nghĩa là đồng xu thứ ngửa mặt sấp, còn nghĩa là đồng xu thứ ngửa mặt ngửa.
- Sau đó, máy tính các giá trị sau:
- là số vị trí mà ;
- là số vị trí mà .
- Tiếp theo, người chơi nhấn một trong hai nút: nút "?" để hỏi, hoặc nút "!" để đoán dãy đồng xu bí mật.
- Sau khi một trong hai nút được nhấn, máy phản hồi như sau:
- Nếu nút "?" được nhấn: máy nhả ra một đồng xu mặt ngửa nếu , và nhả ra một đồng xu mặt sấp nếu .
- Nếu nút "!" được nhấn: máy nhả ra toàn bộ đồng xu bên trong nếu . Máy sẽ bị khóa nếu , và người chơi không thể tương tác với máy được nữa.
Bạn có đủ đồng xu để tương tác với máy tối đa lần, tính cả các lần hỏi và lần đoán. Bạn có thể nghĩ ra chiến lược để lấy được toàn bộ đồng xu từ máy trò chơi của MofK không?
Tương tác
Trong bài này, ban giám khảo đóng vai trò máy trò chơi của MofK, còn chương trình của bạn đóng vai trò người chơi.
Trước khi quá trình tương tác bắt đầu, bạn cần đọc một số nguyên lẻ (): số đồng xu bí mật mà MofK đã đặt vào máy. Sau đó bạn có thể tương tác với chương trình của ban giám khảo như sau.
Nếu bạn quyết định bỏ đồng xu vào máy rồi nhấn nút "?" để hỏi:
- Đầu tiên, in ra một dòng "? x" (không có dấu ngoặc kép), trong đó là một xâu nhị phân độ dài mô tả trạng thái các đồng xu bạn bỏ vào máy theo quy ước ở trên.
- Sau đó, đọc một số () mô tả trạng thái của đồng xu mà máy nhả ra: nghĩa là máy nhả ra đồng xu mặt ngửa, nghĩa là máy nhả ra đồng xu mặt sấp.
Nếu bạn quyết định bỏ đồng xu vào máy rồi nhấn nút "!" để đoán dãy đồng xu:
- Đầu tiên, in ra một dòng "! x" (không có dấu ngoặc kép), trong đó là một xâu nhị phân độ dài mô tả trạng thái các đồng xu bạn bỏ vào máy theo quy ước ở trên.
- Sau đó, quá trình tương tác kết thúc ngay lập tức. Chương trình của bạn phải kết thúc.
Trạng thái của các đồng xu bí mật trong máy được cố định trước khi quá trình tương tác bắt đầu và không thay đổi trong suốt quá trình tương tác.
Sau khi in mỗi dòng, đừng quên in ký tự xuống dòng và flush đầu ra: dùng fflush(stdout) hoặc cout.flush() (hoặc endl) trong C++, System.out.flush() trong Java, sys.stdout.flush() trong Python.
Ràng buộc
- , lẻ.
- Tối đa lần tương tác, tính cả lần đoán.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 1 0 1 0 |
? 000 ? 100 ? 110 ? 101 ! 101 |
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. Xâu bí mật là . Với , chỉ có vị trí khớp nên máy nhả đồng xu mặt ngửa (); với , có vị trí khớp nên máy nhả đồng xu mặt sấp (); với có vị trí khớp; với có vị trí khớp. Cuối cùng chương trình đoán đúng . Đề gốc minh họa một cách tương tác khác: hỏi cả xâu độ dài rồi mới đoán. |
| 5 1 1 0 0 1 1 0 |
? 00000 ? 11000 ? 11100 ? 01100 ? 10100 ? 11110 ? 11101 ! 01101 |
Ví dụ bổ sung (không có trong đề gốc), xâu bí mật là . |
Bình luận