Universal Cup Judging System

Universal Cup

حد الوقت: 5 s حد الذاكرة: 2048 MB مجموع النقاط: 100 تفاعلية
الإحصائيات

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

在游戏开始前,双方约定游戏的轮数以及棋盘的初始状态。最多有 8 个方格可以被标记为“不可用”。双方还要确定谁担任逃跑者,谁担任捕获者。随后,逃跑者在所有可用(即未被标记为不可用)的方格中秘密选择一个起始方格,但不会告知捕获者。

每一轮游戏按顺序包含以下步骤:

  1. 捕获者公开选择可用方格的一个子集(允许为空集),并询问逃跑者:“你目前是否在这些方格中的任意一个里?”

  2. 逃跑者如实回答他们是否在所选方格中。

  3. 捕获者公开选择恰好一个可用方格。该方格在游戏剩余时间内变为不可用。(逃跑者可能当前正位于该方格中;如果是这样,不会发生特殊情况。)

  4. 逃跑者秘密地从当前方格移动到一个正交相邻的可用方格。如果不存在这样的方格,逃跑者宣布他们被困住,捕获者赢得游戏。

如果逃跑者在最后一轮结束时未被困住,他们通过揭示自己选择的起始方格以及每一轮所做的移动,向捕获者证明他们如实回答了所有问题。此时逃跑者赢得游戏。

由于逃跑者最初选择的方格是秘密的,且其后续所有移动也是秘密的,逃跑者被允许通过不真正固定在一个方格上来“作弊”。在游戏结束时,如果逃跑者能给出一套起始方格选择和后续移动,使得这些移动不会导致被困住,且与每一轮中对捕获者问题的回答一致,那么这就足以让逃跑者赢得游戏。

交互

这是一个交互式问题。给定游戏轮数和初始标记为不可用的方格集合,确定在最优策略下是逃跑者还是捕获者获胜,并通过扮演该角色与评测机进行对战来证明这一点。评测机将遵守所有游戏规则,但可能不会采取最优策略。

交互开始时,读取一行包含 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$),列出捕获者所选子集中的方格编号。这些编号保证互不相同,且所有选定的方格保证是可用的。

  • 打印一行输出,包含字符串 YesNo。前者告知捕获者你当前在所选方格中,后者告知捕获者你不在其中。

  • 读取一行,包含一个整数 $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

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.