Tìm manh mối!
Đề bài
Mô tả
Ra đời vào những năm 1940 tại Vương quốc Anh, Cluedo là một trong những trò chơi cờ bàn phổ biến nhất thế giới. Mục tiêu của trò chơi là xác định ai đã sát hại ông Body, hung khí là gì và vụ án xảy ra ở đâu. Trò chơi dùng một bộ bài gồm sáu lá người (ký hiệu A, B, ..., F), sáu lá hung khí (ký hiệu G, H, ..., L) và chín lá phòng (ký hiệu M, N, ..., U). Khi bắt đầu, người ta chọn ngẫu nhiên một lá người, một lá hung khí và một lá phòng rồi rút khỏi bộ bài sao cho không ai nhìn thấy: ba lá này là hung thủ, hung khí và nơi xảy ra án mạng. lá còn lại được xáo và chia lần lượt cho các người chơi, bắt đầu từ người chơi , rồi tới người bên phải cô là người chơi , và cứ thế. Có thể có người chơi nhận nhiều hơn người khác một lá. Trong bài này có bốn người chơi, nên người bên phải người chơi là người chơi .
Phần còn lại của trò chơi là đi tìm manh mối. Các người chơi lần lượt chơi, bắt đầu từ người chơi và đi về bên phải. Mỗi lượt gồm việc đưa ra một giả thuyết (gồm một nghi phạm, một hung khí và một phòng) và hỏi những người chơi khác xem họ có bằng chứng bác bỏ giả thuyết đó hay không. Ví dụ, bạn có thể nói với một người chơi khác "Tôi tin rằng hung thủ là người A, dùng hung khí L, trong phòng T." Nếu người chơi kia cầm đúng một trong các lá này, người đó phải cho bạn (và chỉ bạn) xem lá đó. Nếu họ có nhiều hơn một lá như vậy, họ có thể cho bạn xem lá bất kỳ trong số đó.
Khi đưa ra giả thuyết, bạn phải hỏi người ở bên phải mình trước. Nếu họ không có bằng chứng, bạn tiếp tục hỏi người bên phải họ, và cứ thế, cho tới khi có người có bằng chứng, hoặc không ai có lá nào trong giả thuyết của bạn.
Nhiều khi bạn thu được thông tin ngay cả khi không phải là người đưa ra giả thuyết. Giả sử trong ví dụ trên, bạn là người chơi thứ ba và đang cầm lá A và lá T. Nếu có người khác đưa bằng chứng cho người đưa giả thuyết, bạn biết đó phải là lá hung khí L. Theo dõi các giả thuyết và việc ai đã đưa bằng chứng ở mỗi lượt là một chiến thuật quan trọng của trò chơi.
Để thắng, bạn phải đưa ra một lời buộc tội, trong đó bạn nêu dự đoán cuối cùng về hung thủ, hung khí và căn phòng. Sau khi buộc tội, bạn xem ba lá bài được rút ra lúc đầu: nếu chúng khớp với lời buộc tội, bạn thắng! Dĩ nhiên bạn muốn hoàn toàn chắc chắn trước khi buộc tội.
Đây là bài toán của bạn. Bạn là người chơi . Cho biết các lá bài bạn được chia và lịch sử các giả thuyết cùng bằng chứng, hãy xác định bạn đã gần tới mức có thể buộc tội đến đâu.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên , số giả thuyết đã được đưa ra trong ván chơi. Dòng tiếp theo chứa năm lá bài bạn được chia, là các chữ cái in hoa trong khoảng từ A tới U.
dòng tiếp theo, mỗi dòng mô tả một giả thuyết, theo đúng thứ tự các lượt chơi (giả thuyết đầu tiên do người chơi đưa ra, giả thuyết thứ hai do người chơi , ...). Mỗi dòng bắt đầu bằng ba ký tự là giả thuyết (theo thứ tự người, hung khí, phòng), tiếp theo là câu trả lời của tối đa ba người chơi, bắt đầu từ người chơi ở bên phải người đưa giả thuyết. Nếu một người chơi không đưa bằng chứng thì ghi - (dấu gạch ngang); ngược lại ghi một "ký tự bằng chứng". Nếu bạn nhìn thấy lá bằng chứng cụ thể (vì bạn là người đưa ra nó hoặc là người nhận nó) thì ký tự bằng chứng là chính lá bài đó; ngược lại ký tự bằng chứng là *. Chỉ câu trả lời cuối cùng mới có thể là ký tự bằng chứng. Các ký tự được phân cách bởi đúng một dấu cách. Dữ liệu vào chỉ chứa các chuỗi giả thuyết và câu trả lời hợp lệ.
Dữ liệu ra
In ra một xâu ba ký tự cho biết hung thủ, hung khí và căn phòng. Nếu xác định được hung thủ, in chữ cái tương ứng với người đó; ngược lại in ?. Làm tương tự với hung khí và căn phòng.
Ràng buộc
- .
- Các lá bài là các chữ cái in hoa từ
AtớiU: người từAtớiF, hung khí từGtớiL, phòng từMtớiU. - Năm lá bài của bạn đôi một khác nhau.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 B I P C F A G M - - - |
AGM | Bạn đưa ra giả thuyết A, G, M và không ai có lá nào trong ba lá này. Bạn cũng không cầm chúng, nên đó chính là ba lá bị rút ra. |
| 2 A B C D H F G M M F H M - * |
E?? | Người chơi cho bạn xem lá M. Ở lượt thứ hai, người chơi không có F, H, M; bạn cầm H và người chơi cầm M nên người chơi cầm F. Vậy lá người duy nhất chưa có chủ là E. |
| 3 A C M S D B G S - G A H S - - S C J S * |
??? | Chưa đủ thông tin để xác định lá nào trong ba lá bị rút ra. |
Bình luận