#P15684. [ICPC 2023 Jakarta R] Cursed Game

[ICPC 2023 Jakarta R] Cursed Game

说明

你在仓库中发现了一个古老的盒子,并决定打开它。就在你打开盒子的那一刻,它把你拖入了一个诅咒游戏,你将与一个恶魔对抗。游戏共进行 333333 轮,你必须赢得所有轮次才能逃脱。恶魔还给了你 999999 枚硬币,你可以在所有轮次中使用。

请注意,在本问题中,将网格的单元格 (r,c) (r, c) 定义为网格中第 rr 行第 cc 列的单元格。

在每一轮开始前,恶魔会准备一张秘密纸张,它可以表示为一个 3333 列的网格,行和列都从 1133 编号。恶魔会秘密地在其中一个或多个单元格上打洞,而你并不知道哪些单元格有洞。然后,该轮以恶魔给你一个奇数 NN3N333 \leq N \leq 33)开始。

在每一轮中,你可以向恶魔提出若干次询问,每次询问会花费你一枚硬币。对于每次询问,你可以给恶魔你的纸张,它可以表示为一个 NNNN 列的网格,行和列都从 11NN 编号。每个单元格由你涂成黑色或白色。

对于你的每次询问,恶魔会计算一个二进制结果网格,它有 N2N - 2 行和 N2N - 2 列,行和列都从 11N2N - 2 编号。结果网格中单元格 (r,c) (r, c) 的值按如下方式填充。

  • 恶魔会将秘密纸张覆盖在你的纸张上,使得你的纸张的单元格 (r+i1,c+j1) (r + i - 1, c + j - 1) 与秘密纸张的单元格 (i,j) (i, j) 对齐,其中 1i,j31 \leq i, j \leq 3
  • 只有当秘密纸张中对应的单元格有洞时,恶魔才能看到你纸张中该单元格的颜色。
  • 结果网格中单元格 (r,c) (r, c) 的值为 11,如果恶魔通过洞看到的黑色单元格数量为奇数;否则为 00

如果你赢得该轮,当且仅当结果网格中的所有值都是 11。否则,恶魔会将结果网格作为反馈给你,该轮继续。

如果你花光了所有硬币仍未赢得所有轮次,那么你将永远被困住。请逃脱这个诅咒游戏!

交互过程

每一轮以一个可以通过标准输入读取的奇数 NN3N333 \leq N \leq 33)开始。

然后,对于你向恶魔提出的每次询问,你可以向标准输出输出 NN 行。每行包含 NN 个字符。第 rr 行的第 cc 个字符代表你纸张中单元格 (r,c)(r, c) 的颜色。如果 (r,c)(r, c) 被涂成黑色,字符应为 11;如果涂成白色,字符应为 00

恶魔将回复一行一个字符串,可以通过标准输入读取。

  • 如果字符串是 CORRECT,那么你赢得了当前轮次,并且下一轮(如果存在)将立即开始。
  • 如果字符串是 INCORRECT,那么恶魔将再给出 N2N - 2 行,可以通过标准输入读取。这 N2N - 2 行每行包含 N2N - 2 个字符,代表题目描述中解释的二进制结果网格。

恶魔在每轮开始前准备秘密纸张。换句话说,评测程序是非自适应的。秘密纸张中至少有一个洞。

所有 333333 轮的总询问次数不应超过 999999。如果你超过了最大询问次数,你应该终止你的程序并返回 00 以收到 Wrong Answer 的判定。如果你不终止,由于你的程序正在从已关闭的流中读取,评测结果将是未定义的。

不要忘记在每次输出后刷新输出缓冲区。在 C 语言中,你可以使用 fflush(stdout)。在 C++ 中,你可以使用 fflush(stdout)cout << flush。在 Java 中,你可以对输出流使用 flush 方法,例如 System.out.flush()。在 Python 中,你可以使用 stdout.flush()



提示

样例交互 #1

以下交互只展示了 22 轮。实际的交互会持续到你赢得所有 333333 轮或用完硬币为止。

:::align{center} :::

对样例交互 #1 的解释

对于第一轮,下图展示了恶魔如何为第一次和第二次询问找到结果网格中单元格 (1,1)(1, 1) 的值。灰色方块代表秘密纸张,圆圈代表洞。在第一次询问中,通过洞可以看到 44 个黑色单元格,因此结果网格中单元格 (1,1)(1, 1) 的值为 00。在第二次询问中,通过洞可以看到 55 个黑色单元格,因此结果网格中单元格 (1,1)(1, 1) 的值为 11。由于结果网格全为 1,第一轮结束。

:::align{center} :::

对于第二轮,下图展示了恶魔如何为第一次询问找到结果网格中单元格 (2,1)(2, 1) 的值。由于通过洞可以看到 22 个黑色单元格,单元格 (2,1)(2, 1) 的值为 00

:::align{center} :::

翻译由 DeepSeek V3 完成