QOJ.ac

QOJ

حد الوقت: 9 s حد الذاكرة: 1024 MB مجموع النقاط: 100

#1653. 代號

الإحصائيات

Karen 和她的朋友們正在參加一場高風險的桌遊錦標賽,遊玩熱門遊戲《機密代號》(Codenames)。《機密代號》是一款由兩個對立隊伍進行的遊戲:紅隊與藍隊。Karen 是紅隊的一員。

遊戲在一個 $5 \times 5$ 的棋盤上進行,其中 25 個格子中的每一個都被(秘密地)分配了四種種類之一。棋盤上每種種類的格子數量是固定的:

  • 9 個紅色格子 (r);
  • 8 個藍色格子 (b);
  • 7 個中立格子 (n);
  • 1 個刺客格子 (x)。

格子的真實種類只有每個隊伍的一名玩家(稱為「情報員」)知道。其他玩家最初只看到一個充滿覆蓋格子的 $5 \times 5$ 網格。隨著遊戲進行,格子會被揭開。每個被覆蓋的格子都包含一個物體的名稱(這對本題來說並不重要)。

幸運的是,Karen 是她隊伍的情報員,因此她知道棋盤的真實配置。她的職責是幫助隊友找出紅色格子,同時讓他們遠離所有其他格子(特別是刺客格子)。她可以透過發布一個提示來做到這一點,該提示包含:

  • 一個有效的單字 $w$(來自一個包含 $n$ 個單字的字典);
  • 一個正整數 $g$(隊友應該進行的猜測次數)。

她的隊友隨後會根據提示,嘗試猜測盡可能多的紅色格子。他們從第一次猜測開始,揭開其中一個格子。如果揭開的格子是紅色的,他們可以繼續猜測;否則,他們的回合結束,由另一隊開始他們的回合。如果一個隊伍揭開了所有對應顏色的格子,或者另一隊揭開了刺客格子,該隊伍就贏得遊戲。

為了說明這一點,讓我們考慮下方的遊戲狀態(對應範例的狀態)。左圖顯示了 Karen 眼中的棋盤。中間的圖顯示了她隊友眼中的棋盤。請注意,對於 Karen 的隊友來說,有些格子是被覆蓋的,只有 Karen 知道它們的真實種類。右圖的含義將在後文中解釋。

最初,Karen 的目標是提供與某些紅色格子中描述的物體名稱相關的提示,以便隊友知道只揭開那些格子。然而,她很快意識到遊戲進展並不順利,藍隊可能會在下一回合擊敗他們。值得慶幸的是,她和她的朋友們專門為這些情況設計了一種秘密的「緊急作弊方案」。

他們首先為 25 個格子中的每一個分配一個字母,按列優先順序排列(如上圖右側所示)。然後,當 Karen 發布一個單字 $w$ 和一個數字 $g$ 時,她的隊友會執行以下操作:

  1. 依序遍歷單字 $w$ 的每個字母 $w_i$;
  2. 如果 $w_i$ 沒有分配給任何格子,或者 $w_i$ 對應的格子已經被揭開,則什麼都不做;否則,猜測 $w_i$ 對應的格子。

隊友重複此過程,直到他們揭開所有正確的格子、犯了錯誤(揭開非紅色格子)、已經進行了所有 $g$ 次猜測,或者單字 $w$ 的所有字母都已被揭開。

在上面的範例中,Karen 可以向她的隊伍宣布「actor 2」。她的隊伍會先猜測格子 $(1, 1)$(對應字母 a),跳過字母 c(因為格子 $(1, 3)$ 已經被揭開),然後猜測格子 $(4, 5)$,從而贏得遊戲(因為其他紅色格子已經被揭開)。

Karen 希望利用這個方案在一回合內贏得遊戲。她知道所有 $n$ 個有效單字的字典,以及遊戲的當前狀態。找出她應該向隊伍宣布的某個提示,以帶領他們取得勝利!

你需要解決 $q$ 個不同的場景。字典對於所有場景都是相同的,但棋盤配置可能不同。

輸入格式

第一行包含一個正整數 $n$ ($1 \le n \le 100\,000$),代表有效單字的數量。接下來的 $n$ 行,每行包含一個長度至少為 1 且最多為 30 個字母的字串,代表字典中的單字。

接下來的一行包含一個正整數 $q$ ($1 \le q \le 100\,000$),代表場景的數量。接著有 $q$ 行,每行描述一個棋盤。每個棋盤由一個 $5 \times 5$ 的字母網格表示,字母來自集合 $\{r, b, n, x\}$(紅/藍/中立/刺客)。如果字母是大寫的,則表示該格子已經被揭開(否則該格子是被覆蓋的)。至少有一個藍色和一個紅色的被覆蓋格子,且刺客格子總是處於被覆蓋狀態;換句話說,狀態總是表示遊戲尚未結束。

輸出格式

對於每個場景,輸出一個由單字 $w$ 和數字 $g$ ($1 \le g \le 9$) 組成的提示,使 Karen 的隊伍獲勝。如果對於特定場景無法宣布這樣的提示,則輸出單字 “IMPOSSIBLE”(不含引號)來代替提示。如果存在多個解,則接受其中任何一個。不同場景的答案應列印在不同的行上。

範例

輸入 1

3
actor
cheat
zeta
1
rBBnR
NRnbB
nRRnR
NRxBr
nBRbB

輸出 1

actor 2

說明

請注意,Karen 不能宣布例如 cheat 3,因為她的隊伍最終會揭開位置 $(2, 3)$ 的格子並結束他們的回合。其他一些正確的解法包括 zeta 2 或 actor 4。

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#313EditorialOpen题解jiangly2025-12-14 07:02:53View

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.