Entrapment 是一个在 $3 \times 3$ 方格棋盘上进行的非对称双人游戏。两名玩家分别称为“逃跑者”(Runner)和“捕获者”(Trapper)。棋盘方格编号如下:
在游戏开始前,双方约定游戏的轮数以及棋盘的初始状态。最多有 8 个方格可以被标记为“不可用”。双方还要确定谁担任逃跑者,谁担任捕获者。随后,逃跑者在所有可用(即未被标记为不可用)的方格中秘密选择一个起始方格,但不会告知捕获者。
每一轮游戏按顺序包含以下步骤:
捕获者公开选择可用方格的一个子集(允许为空集),并询问逃跑者:“你目前是否在这些方格中的任意一个里?”
逃跑者如实回答他们是否在所选方格中。
捕获者公开选择恰好一个可用方格。该方格在游戏剩余时间内变为不可用。(逃跑者可能当前正位于该方格中;如果是这样,不会发生特殊情况。)
逃跑者秘密地从当前方格移动到一个正交相邻的可用方格。如果不存在这样的方格,逃跑者宣布他们被困住,捕获者赢得游戏。
如果逃跑者在最后一轮结束时未被困住,他们通过揭示自己选择的起始方格以及每一轮所做的移动,向捕获者证明他们如实回答了所有问题。此时逃跑者赢得游戏。
由于逃跑者最初选择的方格是秘密的,且其后续所有移动也是秘密的,逃跑者被允许通过不真正固定在一个方格上来“作弊”。在游戏结束时,如果逃跑者能给出一套起始方格选择和后续移动,使得这些移动不会导致被困住,且与每一轮中对捕获者问题的回答一致,那么这就足以让逃跑者赢得游戏。
交互
这是一个交互式问题。给定游戏轮数和初始标记为不可用的方格集合,确定在最优策略下是逃跑者还是捕获者获胜,并通过扮演该角色与评测机进行对战来证明这一点。评测机将遵守所有游戏规则,但可能不会采取最优策略。
交互开始时,读取一行包含 2 个空格分隔的整数 $R$ 和 $U$ ($1 \le R \le 9, 0 \le U \le 8, R + U \le 9$):游戏的轮数和游戏开始时不可用的方格数量。
接下来,如果 $U > 0$,读取一行包含 $U$ 个空格分隔的整数 $s$ ($1 \le s \le 9$):游戏开始时不可用的方格编号。请参考上方的图示了解棋盘方格的编号方式。这 $U$ 个编号保证互不相同。
确定在最优策略下逃跑者还是捕获者会获胜。如果逃跑者在最优策略下获胜,打印一行包含字符串 Runner;否则打印 Trapper。在游戏的剩余部分,你将扮演该角色;请参阅下文了解在该角色下与评测机交互的进一步说明。
对于逃跑者,重复以下步骤 $R$ 次:
读取一行输入,包含一个整数 $N$:捕获者选择询问的可用方格子集的大小。$N$ 保证在 0 到棋盘上剩余可用方格总数之间(含边界)。
如果 $N > 0$,读取一行包含 $N$ 个空格分隔的整数 $\ell$ ($1 \le \ell \le 9$),列出捕获者所选子集中的方格编号。这些编号保证互不相同,且所有选定的方格保证是可用的。
打印一行输出,包含字符串
Yes或No。前者告知捕获者你当前在所选方格中,后者告知捕获者你不在其中。读取一行,包含一个整数 $i$ ($1 \le i \le 9$),即捕获者标记为不可用的方格编号。保证方格 $i$ 是之前可用的方格。
打印一行字符串
Free以告知捕获者你已秘密移动到一个正交相邻的可用方格,并准备好进入下一轮。如果没有正交相邻的可用方格,你必须打印Trapped并退出;你的提交将被判定为错误,因为未能躲避捕获者。
在按照上述协议完成 $R$ 轮游戏后,打印一行包含 $R + 1$ 个空格分隔的整数。第一个整数是你选择的起始方格编号;接下来的 $R$ 个整数分别是你在每一轮结束时移动到的方格编号。你的移动必须合法,且必须与你在每一轮中对捕获者查询的回答一致。打印此行后,你的程序必须退出。
对于捕获者,重复以下步骤 $R$ 次:
打印一行,包含一个整数 $N$:你想要询问逃跑者的可用方格子集的大小。
如果 $N > 0$,打印一行包含 $N$ 个空格分隔的整数,列出要询问逃跑者的可用方格。你可以按任意顺序列出编号,但编号必须互不相同且必须指向可用方格。
读取一行输入,包含一个字符串:如果逃跑者在你选择的方格中,则为
Yes,否则为No。打印一行,包含一个整数 $i$:你标记为不可用的方格。编号 $i$ 必须是一个当前有效的可用方格。
读取一行输入,包含一个字符串:如果逃跑者已移动到可用方格,则为
Free;如果他们无法移动,则为Trapped。读取到Trapped后,你赢得了游戏,程序必须退出。如果你在第 $R$ 轮结束时读取到Free,程序也必须退出,但你的提交将被判定为错误,因为你未能困住逃跑者。
评测机保证如实回答所有问题。
说明
请务必在打印每一行后刷新输出流,并在交互完成后干净地退出。请确保严格遵循上述交互协议,特别是关于在每一行输出中打印什么信息:例如,如果协议要求你在单行中打印一系列空格分隔的整数,评测机将不会接受每个整数单独占一行。
如果评测机收到无效或意外的输入,它将打印 $-1$ 并立即退出。你的程序必须检测到此错误报告并干净地退出,以获得 Wrong Answer 判决。如果你的程序阻塞等待评测机的进一步交互,或者试图将 $-1$ 解释为游戏移动,你可能会收到其他拒绝判决(如 Time Limit Exceeded 或 Runtime Error)而不是 Wrong Answer。
样例
输入格式 1
3 6 1 2 3 7 8 9
输出格式 1
Trapper 2 4 5 5 0 6
输入格式 2
2 0
输出格式 2
Runner 7 3 1 2 8 9 4 5 Yes 5 Free 4 4 6 7 8 Yes 7 Free 5 4 1