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ó 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:
- Trong Phòng chơi có chiếc hộp rỗng giống hệt nhau, được đánh số . 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.
- Đầ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).
- 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 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ì Phòng chơi sẽ có Phòng chơi liên tiếp. Alice sau khi xong Phòng chơi thứ sẽ ra ngoài và chờ Bob hoàn thành lượt của mình ở phòng thứ . 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 giai đoạn:
- Chương trình chấm chuẩn bị hộp và cờ, rồi in ra số nguyên ().
- Chương trình của bạn in ra dòng, dòng thứ chứa một biểu thức toán học (mô tả ở dưới). Biểu thức thứ nói với Bob rằng: NẾU giá trị của biểu thức này khác (đúng), thì phần thưởng nằm ở hộp thứ . Đâ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ả phòng.
- Chương trình chấm in ra (): số Phòng chơi.
- Với mỗi phòng:
- Chương trình chấm in ra một dòng gồm giá trị hoặc cách nhau bởi dấu cách, giá trị thứ là màu của lá cờ thứ ( là Xanh, 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 (): 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ả 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òngBAD; 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á ký tự.
- Toán hạng có thể là số nguyên, hoặc với để lấy màu của lá cờ trên hộp thứ : nếu cờ màu Xanh, 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ả nếu đúng và 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á . Chia hoặc chia lấy dư cho bị coi là sai.
- Giá trị được coi là sai, mọi số nguyên khác được coi là đúng. Với mọi trạng thái cờ (sau khi Alice đổi màu), phải có đúng biểu thức đúng và 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ứ trong chiến lược của bạn là ([1] + [2] + [3]) * 2 = 6 thì Bob sẽ mở hộp thứ 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
- Mỗi biểu thức dài không quá ký tự, mọi giá trị trung gian có giá trị tuyệt đối không quá .
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 nếu cờ màu Xanh, hộp nếu cờ màu Đỏ. Phòng : cờ , phần thưởng ở hộp ; Alice đổi cờ thành , cờ vẫn Xanh nên Bob mở hộp . Phòng : cờ , phần thưởng ở hộp ; Alice đổi cờ thành , cờ Đỏ nên Bob mở hộp . 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 và của rồi ghép thành số hiệu hộp. Phòng : cờ thành sau khi Alice đổi cờ ; lẻ, chẵn, nên chỉ biểu thức đúng. Phòng : cờ thành , mọi tổng đều chẵn nên chỉ biểu thức đúng. |
Bình luận