#P12622. [ICPC 2025 NAC] Entrapment
[ICPC 2025 NAC] Entrapment
Description
Entrapment 是一款非对称的双人游戏,在一个 的方格棋盘上进行。两名玩家分别称为 Runner(逃亡者)和 Trapper(追捕者)。棋盘方格编号如下:
$$\begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 4 & 5 & 6 \\ \hline 7 & 8 & 9 \\ \hline \end{array}$$游戏开始前,玩家需约定游戏轮数 和初始棋盘状态。最多有 个方格可被标记为 不可用。玩家还需确定谁扮演 Runner,谁扮演 Trapper。Runner 会秘密选择一个可用的起始方格(未被标记为不可用的方格),但不会告知 Trapper。
每轮游戏按以下顺序进行:
- Trapper 公开选择一个可用方格的子集(允许空集),并询问 Runner:"你当前是否在这些方格中?"
- Runner 必须如实回答"是"或"否"。
- Trapper 公开选择一个可用方格,该方格在后续游戏中变为不可用。(Runner 可能正位于该方格,此时无特殊效果)
- Runner 秘密移动到当前方格的相邻可用方格(上下左右相邻)。若无可用相邻方格,Runner 宣布被捕获,Trapper 获胜。
若游戏结束时 Runner 未被捕获,需向 Trapper 证明自己始终诚实:公开起始方格和每轮移动路径。此时 Runner 获胜。
由于 Runner 的初始选择和移动路径都是秘密的,Runner 可以通过"作弊"(不真正固定位置)来规避追捕。只要最终能提供符合所有回答的合法移动路径,Runner 即可获胜。
Input Format
交互说明
本题为交互题。给定游戏轮数 和初始不可用方格集合,判断在最优策略下 Runner 或 Trapper 谁能获胜,并作为该角色与评测机对战。评测机会遵守游戏规则,但不保证采用最优策略。
交互开始时,首先读取一行两个整数 和 (,,),分别表示游戏轮数和初始不可用方格数量。
若 ,接着读取一行 个空格分隔的整数 (),表示初始不可用方格的编号(参见上方编号图示)。保证这些编号互不相同。
判断最优策略下的获胜方,输出一行字符串 (Runner 必胜)或 (否则)。之后将作为该角色继续交互:
作为 Runner 时,重复以下步骤 次:
- 读取一个整数 表示 Trapper 询问的方格数量()
- 若 ,读取一行 个空格分隔的整数 ,表示被询问的方格编号(保证编号合法且可用)
- 输出 或 回答是否位于被询问方格中
- 读取一个整数 表示 Trapper 标记为不可用的方格(保证该方格当前可用)
- 若有可用相邻方格,输出 ;否则输出 并退出(此时判负)
完成 轮后,输出一行 个空格分隔的整数:起始方格编号和每轮移动的目标方格编号。移动路径必须合法且与之前回答一致,然后退出程序。
作为 Trapper 时,重复以下步骤 次:
- 输出一个整数 表示询问的方格数量
- 若 ,输出一行 个空格分隔的可用方格编号
- 读取 或 作为回答
- 输出一个整数 表示要标记为不可用的方格(必须当前可用)
- 读取 或 :若为后者则获胜并退出;若完成 轮后 Runner 仍自由则判负
评测机保证所有回答真实有效。
注意:每次输出后需刷新输出流,交互结束后需立即退出。若评测机收到非法输入会输出 并退出,此时程序必须检测该错误并退出以避免错误判定。
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
京公网安备 11011102002149号