trang chủ / đề bài / icpc23_nat_m

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ó n đồ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 s độ dài n, trong đó si=0 nghĩa là đồng xu thứ i ngửa mặt sấp, còn si=1 nghĩa là đồng xu thứ i 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 s 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ả n đồng xu bí mật. Mỗi lần tương tác với máy gồm các bước sau:

  1. Đầu tiên, người chơi bỏ n đồ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 x, trong đó xi=0 nghĩa là đồng xu thứ i ngửa mặt sấp, còn xi=1 nghĩa là đồng xu thứ i ngửa mặt ngửa.
  2. Sau đó, máy tính các giá trị sau:
    • cntcorrect là số vị trí i mà si=xi;
    • cntincorrect là số vị trí i mà si≠xi.
  3. 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.
  4. 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 cntcorrect<cntincorrect, và nhả ra một đồng xu mặt sấp nếu cntcorrect>cntincorrect.
    • Nếu nút "!" được nhấn: máy nhả ra toàn bộ đồng xu bên trong nếu cntcorrect=n. Máy sẽ bị khóa nếu cntcorrect<n, 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 1024 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ẻ n (1≤n≤999): 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ỏ n đồ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 đó x là một xâu nhị phân độ dài n 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ố c (c∈{0,1}) mô tả trạng thái của đồng xu mà máy nhả ra: c=1 nghĩa là máy nhả ra đồng xu mặt ngửa, c=0 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 đó x là một xâu nhị phân độ dài n 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 s 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

  • 1≤n≤999, n lẻ.
  • Tối đa 1024 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à s=101. Với 000, chỉ có 1 vị trí khớp nên máy nhả đồng xu mặt ngửa (1); với 100, có 2 vị trí khớp nên máy nhả đồng xu mặt sấp (0); với 110 có 1 vị trí khớp; với 101 có 3 vị trí khớp. Cuối cùng chương trình đoán đúng 101. Đề gốc minh họa một cách tương tác khác: hỏi cả 8 xâu độ dài 3 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à s=01101.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0