trang chủ / đề bài / icpc23_mt_e

Hộp và cờ

Đề bài

Mô tả

Đây là một bài toán tương tác.

Alice và Bob tham gia một trò chơi giải đố có thưởng. Trò chơi có 2 người chơi là Alice và Bob, cùng một Quản trò. Có hai loại phòng: Phòng chờ và Phòng chơi. Ban đầu Alice và Bob cùng ở Phòng chờ, còn Quản trò ở Phòng chơi.

Trò chơi diễn ra như sau:

  1. Trong Phòng chơi có 2n chiếc hộp rỗng giống hệt nhau, được đánh số 1,2,…,2n. Trên nóc mỗi hộp có một lá cờ chỉ mang một trong hai màu: Xanh hoặc Đỏ. Ban đầu màu của các lá cờ là ngẫu nhiên.
  2. Đầu tiên, Alice bước vào, nhìn trạng thái của tất cả các lá cờ và thấy Quản trò đặt phần thưởng vào một hộp ngẫu nhiên. Sau đó Alice bắt buộc phải chọn đúng một lá cờ và đổi màu nó (từ Xanh sang Đỏ hoặc từ Đỏ sang Xanh).
  3. Sau đó Alice rời phòng mà không gặp Bob, rồi Bob bước vào Phòng chơi. Chỉ dựa vào màu của các lá cờ, Bob phải đoán đúng hộp chứa phần thưởng với duy nhất 1 lần đoán.

Nghe Quản trò giải thích luật, cả hai đều nghĩ trò chơi này là lừa đảo. Nhưng Quản trò khăng khăng rằng có thể thắng, chỉ cần có một chiến lược tốt từ trước. Bạn hãy giúp họ bàn chiến lược nhé.

Ngoài ra, Quản trò không muốn họ thắng nhờ may mắn, nên thay vì 1 Phòng chơi sẽ có T Phòng chơi liên tiếp. Alice sau khi xong Phòng chơi thứ i sẽ ra ngoài và chờ Bob hoàn thành lượt của mình ở phòng thứ i. Nếu Bob đoán đúng, họ lặp lại trò chơi ở phòng tiếp theo; điểm khác nhau duy nhất có thể có là màu các lá cờ và vị trí phần thưởng.

Tương tác

Quá trình tương tác gồm 4 giai đoạn:

  1. Chương trình chấm chuẩn bị 2n hộp và cờ, rồi in ra số nguyên n (1≤n≤6).
  2. Chương trình của bạn in ra 2n dòng, dòng thứ i chứa một biểu thức toán học (mô tả ở dưới). Biểu thức thứ i nói với Bob rằng: NẾU giá trị của biểu thức này khác 0 (đúng), thì phần thưởng nằm ở hộp thứ i. Đây là lúc Alice và Bob thống nhất chiến lược trước khi vào các Phòng chơi; chiến lược chỉ được đưa ra một lần và Bob dùng nó cho cả T phòng.
  3. Chương trình chấm in ra T (1≤T≤100): số Phòng chơi.
  4. Với mỗi phòng:
    • Chương trình chấm in ra một dòng gồm 2n giá trị 0 hoặc 1 cách nhau bởi dấu cách, giá trị thứ j là màu của lá cờ thứ j (0 là Xanh, 1 là Đỏ).
    • Tiếp theo, chương trình chấm in ra một dòng chứa một số nguyên là vị trí hộp mà Quản trò giấu phần thưởng.
    • Chương trình của bạn in ra một số nguyên cpos (1≤cpos≤2n): vị trí lá cờ mà Alice đổi màu.
    • Chương trình chấm đổi màu lá cờ đó rồi tính giá trị của cả 2n biểu thức. Nếu có đúng một biểu thức đúng và đó là biểu thức của hộp chứa phần thưởng, chương trình chấm in ra dòng OK. Ngược lại, nó in ra dòng BAD; khi đó chương trình của bạn nên kết thúc ngay.

Quy định về biểu thức:

  • Độ dài mỗi biểu thức không vượt quá 2506 ký tự.
  • Toán hạng có thể là số nguyên, hoặc [x] với 1≤x≤2n để lấy màu của lá cờ trên hộp thứ x: [x]=0 nếu cờ màu Xanh, [x]=1 nếu cờ màu Đỏ.
  • Các phép toán: cộng +, trừ -, nhân *, chia nguyên / và chia lấy dư %, với cách chia và thứ tự ưu tiên giống như trong ngôn ngữ C++. Có thể dùng dấu ngoặc ( và ).
  • Các phép so sánh = (bằng), > (lớn hơn), < (nhỏ hơn) cho kết quả 1 nếu đúng và 0 nếu sai. Phép = có độ ưu tiên thấp hơn < và >, giống == trong C++.
  • Tại mọi bước tính, giá trị tuyệt đối không được vượt quá 1018. Chia hoặc chia lấy dư cho 0 bị coi là sai.
  • Giá trị 0 được coi là sai, mọi số nguyên khác 0 được coi là đúng. Với mọi trạng thái cờ (sau khi Alice đổi màu), phải có đúng 1 biểu thức đúng và 2n−1 biểu thức sai.
  • Có thể chứng minh luôn tồn tại lời giải thỏa mãn các ràng buộc trên.

Ví dụ, nếu dòng thứ 25 trong chiến lược của bạn là ([1] + [2] + [3]) * 2 = 6 thì Bob sẽ mở hộp thứ 25 khi cả ba lá cờ đầu tiên đều màu Đỏ.

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++, sys.stdout.flush() trong Python.

Ràng buộc

  • 1≤n≤6
  • 1≤T≤100
  • Mỗi biểu thức dài không quá 2506 ký tự, mọi giá trị trung gian có giá trị tuyệt đối không quá 1018.

Ví dụ

Input Output Giải thích
1
2
0 0
1
OK
1 1
2
OK
((([2])%2)=0)=1
((([2])%2)=1)=1
1
1
Cột Input là những gì chương trình chấm in ra, cột Output là những gì chương trình của bạn in ra. Chiến lược: Bob mở hộp 1 nếu cờ 2 màu Xanh, hộp 2 nếu cờ 2 màu Đỏ. Phòng 1: cờ 00, phần thưởng ở hộp 1; Alice đổi cờ 1 thành 10, cờ 2 vẫn Xanh nên Bob mở hộp 1. Phòng 2: cờ 11, phần thưởng ở hộp 2; Alice đổi cờ 1 thành 01, cờ 2 Đỏ nên Bob mở hộp 2. Chiến lược trong đề gốc, [1] - [2] > 0 và [2] > [1] với cùng các lần đổi màu, cũng đúng.
2
2
1 1 1 1
2
OK
0 0 0 0
1
OK
((([2]+[4])%2)=0)+((([3]+[4])%2)=0)=2
((([2]+[4])%2)=1)+((([3]+[4])%2)=0)=2
((([2]+[4])%2)=0)+((([3]+[4])%2)=1)=2
((([2]+[4])%2)=1)+((([3]+[4])%2)=1)=2
2
1
Bob tính tính chẵn lẻ của [2]+[4] và của [3]+[4] rồi ghép thành số hiệu hộp. Phòng 1: cờ 1111 thành 1011 sau khi Alice đổi cờ 2; [2]+[4]=1 lẻ, [3]+[4]=2 chẵn, nên chỉ biểu thức 2 đúng. Phòng 2: cờ 0000 thành 1000, mọi tổng đều chẵn nên chỉ biểu thức 1 đúng.

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