#P12622. [ICPC 2025 NAC] Entrapment

    ID: 12461 远端评测题 5000ms 2048MiB 尝试: 0 已通过: 0 难度: 9 上传者: 标签>搜索2025交互题Special Judge记忆化搜索ICPCNAC

[ICPC 2025 NAC] Entrapment

Description

Entrapment 是一款非对称的双人游戏,在一个 3×33 \times 3 的方格棋盘上进行。两名玩家分别称为 Runner(逃亡者)和 Trapper(追捕者)。棋盘方格编号如下:

$$\begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 4 & 5 & 6 \\ \hline 7 & 8 & 9 \\ \hline \end{array}$$

游戏开始前,玩家需约定游戏轮数 RR 和初始棋盘状态。最多有 88 个方格可被标记为 不可用。玩家还需确定谁扮演 Runner,谁扮演 Trapper。Runner 会秘密选择一个可用的起始方格(未被标记为不可用的方格),但不会告知 Trapper。

每轮游戏按以下顺序进行:

  1. Trapper 公开选择一个可用方格的子集(允许空集),并询问 Runner:"你当前是否在这些方格中?"
  2. Runner 必须如实回答"是"或"否"。
  3. Trapper 公开选择一个可用方格,该方格在后续游戏中变为不可用。(Runner 可能正位于该方格,此时无特殊效果)
  4. Runner 秘密移动到当前方格的相邻可用方格(上下左右相邻)。若无可用相邻方格,Runner 宣布被捕获,Trapper 获胜。

若游戏结束时 Runner 未被捕获,需向 Trapper 证明自己始终诚实:公开起始方格和每轮移动路径。此时 Runner 获胜。

由于 Runner 的初始选择和移动路径都是秘密的,Runner 可以通过"作弊"(不真正固定位置)来规避追捕。只要最终能提供符合所有回答的合法移动路径,Runner 即可获胜。

Input Format

交互说明

本题为交互题。给定游戏轮数 RR 和初始不可用方格集合,判断在最优策略下 Runner 或 Trapper 谁能获胜,并作为该角色与评测机对战。评测机会遵守游戏规则,但不保证采用最优策略。

交互开始时,首先读取一行两个整数 RRUU1R91 \leq R \leq 90U80 \leq U \leq 8R+U9R + U \leq 9),分别表示游戏轮数和初始不可用方格数量。

U>0U > 0,接着读取一行 UU 个空格分隔的整数 ss1s91 \leq s \leq 9),表示初始不可用方格的编号(参见上方编号图示)。保证这些编号互不相同。

判断最优策略下的获胜方,输出一行字符串 Runner\texttt{Runner}(Runner 必胜)或 Trapper\texttt{Trapper}(否则)。之后将作为该角色继续交互:

作为 Runner 时,重复以下步骤 RR 次:

  1. 读取一个整数 NN 表示 Trapper 询问的方格数量(0N可用方格数0 \leq N \leq \text{可用方格数}
  2. N>0N > 0,读取一行 NN 个空格分隔的整数 \ell,表示被询问的方格编号(保证编号合法且可用)
  3. 输出 Yes\texttt{Yes}No\texttt{No} 回答是否位于被询问方格中
  4. 读取一个整数 ii 表示 Trapper 标记为不可用的方格(保证该方格当前可用)
  5. 若有可用相邻方格,输出 Free\texttt{Free};否则输出 Trapped\texttt{Trapped} 并退出(此时判负)

完成 RR 轮后,输出一行 R+1R+1 个空格分隔的整数:起始方格编号和每轮移动的目标方格编号。移动路径必须合法且与之前回答一致,然后退出程序。

作为 Trapper 时,重复以下步骤 RR 次:

  1. 输出一个整数 NN 表示询问的方格数量
  2. N>0N > 0,输出一行 NN 个空格分隔的可用方格编号
  3. 读取 Yes\texttt{Yes}No\texttt{No} 作为回答
  4. 输出一个整数 ii 表示要标记为不可用的方格(必须当前可用)
  5. 读取 Free\texttt{Free}Trapped\texttt{Trapped}:若为后者则获胜并退出;若完成 RR 轮后 Runner 仍自由则判负

评测机保证所有回答真实有效。

注意:每次输出后需刷新输出流,交互结束后需立即退出。若评测机收到非法输入会输出 1-1 并退出,此时程序必须检测该错误并退出以避免错误判定。

Output Format

参见交互说明。

3 6
1 2 3 7 8 9



Yes

Free

No

Trapped


Trapper
2
4 5

5

0

6
2 0

7
3 1 2 8 9 4 5

5

4
4 6 7 8

7

Runner


Yes

Free


Yes

Free
5 4 1