Tôi biết bạn không biết; trước khi bạn nói câu đó tôi không biết, nhưng giờ tôi biết
Đề bài
Mô tả
Claudia tổ chức một trò chơi suy luận cho hai người bạn là Alexia và Bash.
Trò chơi diễn ra trên một lưới gồm hàng và cột. Các hàng được đánh số từ đến từ trên xuống dưới, các cột được đánh số từ đến từ trái sang phải. Ô ở hàng , cột được ký hiệu là . Mỗi ô có màu trắng hoặc đen. Cả Claudia, Alexia và Bash đều biết lưới.
Claudia chọn một ô trắng bí mật, gọi là vị trí. Claudia chỉ cho Alexia biết hàng của vị trí, và chỉ cho Bash biết cột của vị trí. Alexia và Bash là những người suy luận hoàn hảo và không bao giờ nói dối, và tất cả những điều trên đều được mọi người biết.
Sau đó Alexia và Bash trò chuyện với nhau. Họ nói lần lượt từng câu một, theo thứ tự bất kỳ. Đặc biệt, một người có thể nói nhiều câu liên tiếp. Mỗi câu thuộc một trong sáu loại sau, trong đó "bạn" chỉ người còn lại:
- Tôi không biết vị trí.
- Tôi biết vị trí.
- Tôi biết rằng bạn không biết vị trí.
- Tôi không biết liệu bạn có biết vị trí hay không.
- Trước khi bạn nói câu đó, tôi không biết vị trí, nhưng bây giờ tôi biết.
- Nếu bạn nói rằng bạn không biết vị trí, tôi sẽ biết vị trí.
Câu loại 5 chỉ được nói ngay sau một câu của người kia, và "câu đó" chỉ đúng câu cuối cùng này của người kia.
Mỗi câu nói về điều người nói biết tại thời điểm nói, có tính đến tất cả các câu đã nói trước đó. Ở câu loại 4, người nói muốn nói rằng trong số các vị trí người nói cho là có thể, có ít nhất một vị trí mà ở đó người kia sẽ biết vị trí, và có ít nhất một vị trí mà ở đó người kia sẽ không biết. Ở câu loại 6, người nói muốn nói rằng nếu bây giờ người kia nói "Tôi không biết vị trí" thì trong số các vị trí người nói cho là có thể sẽ còn lại đúng một vị trí.
Một cuộc trò chuyện là hợp lệ nếu mọi câu trong đó đều đúng, và sau câu cuối cùng thì cả Alexia, Bash và bất kỳ ai biết lưới và nghe cuộc trò chuyện đều biết vị trí.
Ví dụ, xét lưới hàng, cột sau, các ô trắng là , , và (W là ô trắng, B là ô đen):
| 1 | 2 | 3 | |
|---|---|---|---|
| 1 | B | W | B |
| 2 | W | W | B |
| 3 | B | B | W |
Nếu vị trí là , cuộc trò chuyện sau là hợp lệ:
- Alexia: "Tôi biết rằng bạn không biết vị trí."
- Bash: "Trước khi bạn nói câu đó, tôi không biết vị trí, nhưng bây giờ tôi biết."
Giải thích: lúc đầu Alexia được biết ô bí mật nằm ở hàng , hàng này chỉ có một ô trắng . Bash được biết ô nằm ở cột , cột này có hai ô trắng, nên Bash không biết vị trí. Sau câu của Alexia, Bash biết ô bí mật không thể là : nếu ô bí mật ở hàng thì Alexia sẽ cho rằng là có thể, mà nếu ô bí mật là thì Bash sẽ biết vị trí, nên câu của Alexia sẽ sai. Vậy bây giờ Bash biết ô bí mật là , và câu của Bash là đúng.
Nếu vị trí là , cuộc trò chuyện sau là hợp lệ:
- Alexia: "Nếu bạn nói rằng bạn không biết vị trí, tôi sẽ biết vị trí."
- Alexia: "Tôi không biết vị trí."
- Bash: "Trước khi bạn nói câu đó, tôi không biết vị trí, nhưng bây giờ tôi biết."
Giải thích: Bash chỉ không biết vị trí khi vị trí nằm ở cột , tức là hoặc . Mỗi hàng và chứa đúng một trong hai ô này, còn hàng không chứa ô nào. Vậy câu thứ nhất của Alexia là đúng, và nó cho mọi người biết vị trí không phải . Câu thứ hai của Alexia chỉ đúng với hàng , nên vị trí là hoặc . Bash được biết cột . Ngay trước câu thứ hai của Alexia, cả và đều có thể, còn bây giờ chỉ còn . Nếu vị trí là thì Bash đã biết vị trí từ đầu, nên câu của Bash sẽ sai. Do đó bây giờ mọi người đều biết vị trí là .
Nếu vị trí là , cuộc trò chuyện sau không hợp lệ:
- Alexia: "Tôi biết vị trí."
- Bash: "Tôi biết vị trí."
Giải thích: cả hai câu đều đúng, và cả Alexia lẫn Bash đều biết vị trí. Tuy nhiên người nghe không thể phân biệt vị trí là hay .
Với mỗi ô trắng, hãy xác định xem nếu Claudia chọn ô đó làm vị trí thì có tồn tại một cuộc trò chuyện hợp lệ gồm không quá câu hay không, và nếu có thì hãy tìm một cuộc trò chuyện như vậy.
Dữ liệu vào
Mỗi test gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu (). Tiếp theo là mô tả các bộ dữ liệu.
Dòng đầu tiên của mỗi bộ dữ liệu chứa hai số nguyên và (), số hàng và số cột của lưới.
Mỗi dòng trong dòng tiếp theo chứa một xâu gồm ký tự. Ký tự thứ của dòng thứ là W nếu ô màu trắng, hoặc B nếu ô đó màu đen. Lưới có ít nhất một ô trắng.
Dữ liệu bảo đảm tổng của tất cả các bộ dữ liệu không vượt quá .
Dữ liệu ra
Với bộ dữ liệu thứ , đầu tiên in ra một dòng Case #T:. Sau đó xử lý các ô trắng theo thứ tự hàng tăng dần, các ô cùng hàng theo thứ tự cột tăng dần. Với mỗi ô trắng :
- Nếu không có cuộc trò chuyện hợp lệ nào gồm không quá câu, in ra một dòng gồm ba số nguyên , và .
- Ngược lại, in ra một dòng gồm ba số nguyên , và (), số câu của một cuộc trò chuyện hợp lệ. Sau đó in ra dòng mô tả các câu theo thứ tự. Mỗi dòng chứa chữ cái
Anếu câu do Alexia nói hoặcBnếu câu do Bash nói, viết liền ngay sau đó là loại của câu (một số nguyên từ đến ). Ví dụ,A3nghĩa là Alexia nói "Tôi biết rằng bạn không biết vị trí".
Không cần cực tiểu hóa . Nếu có nhiều cuộc trò chuyện hợp lệ, có thể in ra một cuộc trò chuyện bất kỳ.
Ràng buộc
- .
- .
- Mỗi lưới có ít nhất một ô trắng.
- Tổng của tất cả các bộ dữ liệu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 3 3 BWB WWB BBW |
Case #1: 1 2 2 A3 B5 2 1 2 B3 A5 2 2 3 A6 A1 B5 3 3 -1 |
Lưới trong phần mô tả. Ô và : các cuộc trò chuyện đã giải thích ở trên. Ô đối xứng với ô khi đổi vai trò hàng và cột. Ô : không có cuộc trò chuyện hợp lệ; chẳng hạn sau A2 chỉ còn và , hai ô mà mỗi câu đều cùng đúng hoặc cùng sai. |
| 2 1 1 W 3 3 WWW WWB WBB |
Case #1: 1 1 0 Case #2: 1 1 -1 1 2 3 B3 A1 B5 1 3 1 B2 2 1 3 A3 A1 B5 2 2 2 A3 B2 3 1 1 A2 |
Ví dụ bổ sung (không có trong đề gốc). Bộ 1: chỉ có một ô trắng nên mọi người biết vị trí ngay từ đầu, . Bộ 2, ô : câu A3 đúng ở hàng và (ở hàng có ô , nơi Bash biết vị trí), còn lại , , ; khi đó cột chỉ còn ô nên câu B2 chỉ còn lại ô này. Ô : không có cuộc trò chuyện hợp lệ. |
Bình luận