trang chủ / đề bài / icpc26_nat_i

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 R hàng và C cột. Các hàng được đánh số từ 1 đến R từ trên xuống dưới, các cột được đánh số từ 1 đến C từ trái sang phải. Ô ở hàng r, cột c được ký hiệu là (r,c). 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:

  1. Tôi không biết vị trí.
  2. Tôi biết vị trí.
  3. Tôi biết rằng bạn không biết vị trí.
  4. Tôi không biết liệu bạn có biết vị trí hay không.
  5. 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.
  6. 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 3 hàng, 3 cột sau, các ô trắng là (1,2), (2,1), (2,2) và (3,3) (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à (1,2), cuộc trò chuyện sau là hợp lệ:

    1. Alexia: "Tôi biết rằng bạn không biết vị trí."
    2. 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 1, hàng này chỉ có một ô trắng (1,2). Bash được biết ô nằm ở cột 2, 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à (2,2): nếu ô bí mật ở hàng 2 thì Alexia sẽ cho rằng (2,1) là có thể, mà nếu ô bí mật là (2,1) 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à (1,2), và câu của Bash là đúng.

  • Nếu vị trí là (2,2), cuộc trò chuyện sau là hợp lệ:

    1. Alexia: "Nếu bạn nói rằng bạn không biết vị trí, tôi sẽ biết vị trí."
    2. Alexia: "Tôi không biết vị trí."
    3. 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 2, tức là (1,2) hoặc (2,2). Mỗi hàng 1 và 2 chứa đúng một trong hai ô này, còn hàng 3 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 (3,3). Câu thứ hai của Alexia chỉ đúng với hàng 2, nên vị trí là (2,1) hoặc (2,2). Bash được biết cột 2. Ngay trước câu thứ hai của Alexia, cả (1,2) và (2,2) đều có thể, còn bây giờ chỉ còn (2,2). Nếu vị trí là (2,1) 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à (2,2).

  • Nếu vị trí là (3,3), cuộc trò chuyện sau không hợp lệ:

    1. Alexia: "Tôi biết vị trí."
    2. 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à (1,2) hay (3,3).

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á 200 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 τ (1≤τ≤50). 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 R và C (1≤R,C≤7), số hàng và số cột của lưới.

Mỗi dòng trong R dòng tiếp theo chứa một xâu gồm C ký tự. Ký tự thứ c của dòng thứ r là W nếu ô (r,c) 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 R·C của tất cả các bộ dữ liệu không vượt quá 50.

Dữ liệu ra

Với bộ dữ liệu thứ T, đầ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 (r,c):

  • Nếu không có cuộc trò chuyện hợp lệ nào gồm không quá 200 câu, in ra một dòng gồm ba số nguyên r, c và −1.
  • Ngược lại, in ra một dòng gồm ba số nguyên r, c và k (0≤k≤200), số câu của một cuộc trò chuyện hợp lệ. Sau đó in ra k dòng mô tả các câu theo thứ tự. Mỗi dòng chứa chữ cái A nếu câu do Alexia nói hoặc B nế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ừ 1 đến 6). Ví dụ, A3 nghĩ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 k. 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

  • 1≤τ≤50.
  • 1≤R,C≤7.
  • Mỗi lưới có ít nhất một ô trắng.
  • Tổng R·C của tất cả các bộ dữ liệu không vượt quá 50.

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ả. Ô (1,2) và (2,2): các cuộc trò chuyện đã giải thích ở trên. Ô (2,1) đối xứng với ô (1,2) khi đổi vai trò hàng và cột. Ô (3,3): không có cuộc trò chuyện hợp lệ; chẳng hạn sau A2 chỉ còn (1,2) và (3,3), 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, k=0. Bộ 2, ô (2,2): câu A3 đúng ở hàng 2 và 3 (ở hàng 1 có ô (1,3), nơi Bash biết vị trí), còn lại (2,1), (2,2), (3,1); khi đó cột 2 chỉ còn ô (2,2) nên câu B2 chỉ còn lại ô này. Ô (1,1): không có cuộc trò chuyện hợp lệ.

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