Các quy tắc của trò chơi này có thể hơi khác so với trò chơi chính thức.
Karen và bạn bè đang tham gia một giải vô địch trò chơi trên bàn cờ đầy kịch tính, chơi trò chơi phổ biến Codenames. Codenames là một trò chơi giữa hai đội đối lập: đội đỏ và đội xanh. Karen là thành viên của đội đỏ.
Trò chơi được chơi trên một bàn cờ kích thước $5 \times 5$, trong đó mỗi ô trong số 25 ô được (bí mật) gán cho một trong bốn loại. Có một số lượng cố định các ô thuộc mỗi loại trên bàn cờ: 9 ô đỏ (r); 8 ô xanh (b); 7 ô trung lập (n); 1 ô sát thủ (x).
Loại thực sự của các ô chỉ được biết bởi một người chơi của mỗi đội (gọi là "spymaster"). Những người chơi khác ban đầu chỉ thấy một lưới $5 \times 5$ đầy các ô bị che. Các ô sẽ được tiết lộ khi trò chơi tiến triển. Mỗi ô bị che chứa tên của một đối tượng (điều này hóa ra không liên quan đến bài toán này).
May mắn thay, Karen là spymaster của đội mình, vì vậy cô ấy biết cấu hình thực sự của bàn cờ. Trách nhiệm của cô là giúp đồng đội khám phá các ô đỏ, đồng thời giữ họ tránh xa tất cả các ô khác (đặc biệt là ô sát thủ). Cách cô ấy có thể làm điều đó là đưa ra một gợi ý bao gồm: một từ hợp lệ $w$ (từ một từ điển gồm $n$ từ); một số dương $g$ (số lần đoán mà đồng đội của cô ấy nên thực hiện).
Đồng đội của cô ấy sau đó sẽ cố gắng đoán càng nhiều ô đỏ càng tốt, dựa trên gợi ý. Họ bắt đầu bằng cách thực hiện dự đoán đầu tiên và tiết lộ một trong các ô. Nếu ô được tiết lộ là màu đỏ, họ có thể tiếp tục đoán; nếu không, lượt của họ kết thúc và đội kia bắt đầu lượt của họ. Một đội thắng trò chơi nếu tất cả các ô có màu tương ứng của họ được tiết lộ, hoặc nếu đội kia tiết lộ ô sát thủ.
Để minh họa, hãy xem xét trạng thái trò chơi dưới đây (trạng thái tương ứng với ví dụ). Hình bên trái cho thấy góc nhìn của Karen về bàn cờ. Hình ở giữa cho thấy góc nhìn của đồng đội cô về bàn cờ. Lưu ý rằng một số ô bị che đối với đồng đội của Karen, và chỉ Karen biết loại thực sự của chúng. Ý nghĩa của hình bên phải sẽ được giải thích sau trong bài toán.
Ban đầu, mục tiêu của Karen là đưa ra các gợi ý liên quan đến tên các đối tượng được mô tả trong một số ô đỏ, để đồng đội biết chỉ tiết lộ những ô đó. Tuy nhiên, cô sớm nhận ra rằng trò chơi không diễn ra tốt đẹp, và đội xanh có thể đánh bại họ trong lượt tiếp theo. Rất may, cô và bạn bè đã nghĩ ra một "chiến thuật gian lận khẩn cấp" bí mật cho những tình huống này.
Họ bắt đầu bằng cách gán một chữ cái cho mỗi ô trong số 25 ô, theo thứ tự hàng (như minh họa ở trên, trong hình bên phải). Sau đó, khi Karen công bố một từ $w$ và một số $g$, đồng đội của cô sẽ thực hiện các bước sau:
- Đi qua từng chữ cái $w_i$ của từ $w$ theo thứ tự;
- Nếu $w_i$ không được gán cho bất kỳ ô nào hoặc ô được gán cho $w_i$ đã được tiết lộ, thì không làm gì cả; nếu không, hãy đoán ô tương ứng với $w_i$.
Đồng đội lặp lại quy trình này cho đến khi họ tiết lộ tất cả các ô đúng, họ phạm sai lầm (tiết lộ một ô không phải màu đỏ), họ đã thực hiện đủ $g$ lần đoán, hoặc tất cả các chữ cái của $w$ đã được tiết lộ.
Trong ví dụ trên, Karen có thể công bố "actor 2" cho đội của mình. Đội của cô trước tiên sẽ đoán ô $(1, 1)$ (tương ứng với chữ a), bỏ qua chữ c vì ô $(1, 3)$ đã được tiết lộ, và sau đó đoán ô $(4, 5)$, giành chiến thắng trong trò chơi (vì các ô đỏ khác đã được tiết lộ).
Karen muốn sử dụng chiến thuật này để giành chiến thắng trong một lượt. Cô biết từ điển của tất cả $n$ từ hợp lệ, cũng như trạng thái hiện tại của trò chơi. Hãy tìm ra một gợi ý mà cô ấy nên công bố cho đội của mình để mang lại chiến thắng!
Có $q$ kịch bản khác nhau mà bạn cần giải quyết. Từ điển là giống nhau cho tất cả các kịch bản, nhưng cấu hình bàn cờ có thể khác nhau.
Dữ liệu vào
Dòng đầu tiên của dữ liệu vào chứa một số nguyên dương $n$ ($1 \le n \le 100\,000$), số lượng từ hợp lệ. Mỗi dòng trong số $n$ dòng tiếp theo chứa một chuỗi duy nhất gồm ít nhất một và tối đa 30 chữ cái, đại diện cho các từ trong từ điển.
Dòng tiếp theo chứa một số nguyên dương $q$ ($1 \le q \le 100\,000$), số lượng kịch bản. Sau đó, $q$ dòng tiếp theo, mỗi dòng mô tả một bàn cờ. Mỗi bàn cờ được biểu diễn bằng một lưới $5 \times 5$ các chữ cái từ tập $\{r, b, n, x\}$ (đỏ/xanh/trung lập/sát thủ). Nếu chữ cái là chữ in hoa, điều đó có nghĩa là ô đó đã được tiết lộ (nếu không, ô đó bị che). Có ít nhất một ô xanh và một ô đỏ bị che, và ô sát thủ luôn bị che; nói cách khác, trạng thái luôn chỉ ra một trò chơi chưa kết thúc.
Dữ liệu ra
Đối với mỗi kịch bản trong số $q$ kịch bản, hãy xuất ra gợi ý bao gồm một từ $w$ và một số $g$ ($1 \le g \le 9$) mang lại chiến thắng cho đội của Karen. Nếu không có gợi ý nào như vậy có thể được công bố cho kịch bản cụ thể, hãy in một từ duy nhất "IMPOSSIBLE" (không có dấu ngoặc kép) thay vì gợi ý. Nếu có nhiều giải pháp, bất kỳ giải pháp nào cũng được chấp nhận. Các câu trả lời cho các kịch bản khác nhau nên được in trên các dòng riêng biệt.
Ví dụ
Dữ liệu vào 1
3 actor cheat zeta 1 rBBnR NRnbB nRRnR NRxBr nBRbB
Dữ liệu ra 1
actor 2
Ghi chú
Lưu ý rằng Karen không thể công bố, ví dụ, cheat 3, vì đội của cô ấy sẽ kết thúc bằng việc tiết lộ ô tại vị trí $(2, 3)$ và kết thúc lượt của họ. Một số giải pháp đúng khác có thể là zeta 2 hoặc actor 4.