QOJ.ac

QOJ

Time Limit: 1.0 s Memory Limit: 256 MB Total points: 100 Interactive

#18507. 正方形游戏

Statistics

这是一个交互式问题。在这个问题中,你需要战胜一个随机做出移动的对手。

Felix 和 Sophia 在一个由 $m \times n$ 个正方形格子组成的矩形棋盘上玩游戏。他们轮流进行操作。棋盘上的每个格子要么是空白的,要么是被染色的。最初,所有格子都是空白的。一次移动包括选择任意四个组成 $2 \times 2$ 正方形的空白格子,并将这些格子染色。无法进行移动的玩家输掉游戏。

在 Felix 的每个回合中,他会从所有可能的 $2 \times 2$ 正方形中等概率随机选择一个并将其染色。你的任务是扮演 Sophia。如果你的程序在 300 局游戏中输掉不超过 10 局,则被认为是正确的。

在这个问题中,每个测试点都指定了棋盘的大小。在每个测试点中,你必须恰好玩 300 局游戏。在每局游戏中,Felix 先手,Sophia 后手。

输入格式

第一行包含两个由空格分隔的整数 $m$ 和 $n$:棋盘的大小($16 \le m, n \le 25$)。请注意下限:棋盘不能太小。棋盘的行从 $1$ 到 $m$ 编号,列从 $1$ 到 $n$ 编号。

接下来的输入被分为若干个块,每个块对应一局游戏。每个块以一行 start k 开始,其中 $k$ 是从 1 开始的游戏编号。接下来的每一行格式为 move r c($1 \le r < m, 1 \le c < n$)。这样的一行意味着在 Felix 的回合中,他将坐标为 $(r, c)$、$(r, c + 1)$、$(r + 1, c)$ 和 $(r + 1, c + 1)$ 的四个格子染了色。如果一局游戏以 Sophia 获胜结束,则在 Felix 的下一个回合位置给出的行将是 won,之后该块结束。如果一局游戏以 Felix 获胜结束,则在 Felix 的回合之后的下一行将是 lost,之后该块也结束。

各个块一个接一个地出现,没有任何额外的分隔符。在最后一个块之后,有一行单独的 end

保证 Felix 的所有移动都符合游戏规则,且每次移动都是伪随机且等概率选择的。值得注意的是,在第一局游戏开始之前,伪随机数生成器总是使用相同的值进行初始化。这意味着,如果你的程序作为 Sophia 的策略是确定性的,那么在每次测试中,如果重复运行该程序,所有的移动和所有游戏的结果都将保持不变。

输出格式

在游戏中的每个 Sophia 的回合,且至少存在一个可行移动时,输出一行格式为 move r c($1 \le r < m, 1 \le c < n$)。这样的一行意味着你为 Sophia 选择的移动是将坐标为 $(r, c)$、$(r, c + 1)$、$(r + 1, c)$ 和 $(r + 1, c + 1)$ 的四个格子染色。

为了防止输出缓冲,在输出每行后,请务必执行清空缓冲区的命令。例如,在 C 或 C++ 中可以使用 fflush(stdout),在 Java 中可以使用 System.out.flush(),在 Pascal 中可以使用 flush(output),在 Python 中可以使用 sys.stdout.flush()

如果你的程序做出了无效的移动,或者输掉了超过 10 局游戏,它将在相应的测试点上获得 “Wrong Answer” 的结果。

样例

输入格式 1

2 5
start 1
move 1 4
<waiting for output>
won
start 2
move 1 2
<waiting for output>
won
end

输出格式 1

<reading input>
<reading input>
<reading input>
move 1 1
<reading input>
<reading input>
<reading input>
move 1 4
<reading input>
<terminating>

说明

当评测你的程序时,第一个测试点就是题面中的样例。请注意,该测试点不满足 $m, n \ge 16$ 的限制,但从第二个测试点开始的所有测试点均满足该限制。此外,在样例测试点中,只有 2 局游戏,而不是其他所有测试点中的 300 局游戏。Felix 的移动选择不依赖于 Sophia 的移动,并且是预先确定的。最后,在 $2 \times 5$ 的棋盘上,无论游戏如何进行,后手(Sophia)都必胜。

如果你的程序赢得了两局游戏并在此之后成功终止,则可以通过样例测试。回想一下,对于正式测试点,你的程序需要输掉不超过 10 局游戏并成功终止才能通过。

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.