你在仓库里发现了一个古董盒子并决定打开它。当你打开盒子的那一刻,它就会让你陷入一场被诅咒的游戏,你正在与恶魔对抗。游戏由 $$$333$$$ 回合组成,你必须赢得所有回合才能逃脱。恶魔还会给你 $$$999$$$ 硬币,你可以在所有回合中使用它们。
请注意,在此问题中,将网格的单元格 $$$(r, c)$$$ 表示为网格的行 $$$r$$$ 和列 $$$c$$$ 中的单元格。
在每一轮开始之前,恶魔都会准备一份秘密文件,它可以表示为具有 $$$3$$$ 行和 $$$3$$$ 列的网格,编号从 $$$1$$$ 到 $$$3$$$。恶魔会偷偷地在一个或多个细胞上打一个洞,而你不知道哪些细胞上有一个洞。然后,回合开始时,恶魔会给你一个奇数 $$$N$$$ ($$$3 \leq N \leq 33$$$)。
在每一轮中,你可以向恶魔询问几个问题,每个问题都会花费你一枚硬币。对于每个查询,您可以向恶魔提供您的论文,该论文可以表示为包含 $$$N$$$ 行和 $$$N$$$ 列的网格,编号都从 $$$1$$$ 到 $$$N$$$。每个单元格都由您涂成黑色或白色。
对于您的每个查询,恶魔将计算一个二进制结果网格,其中包含 $$$N - 2$$$ 行和 $$$N - 2$$$ 列,编号均从 $$$1$$$ 到 $$$N - 2$$$。结果网格的单元格 $$$(r, c)$$$ 上的值填充如下。
- 恶魔会将秘密文件放在你的文件上面,使你的文件的单元格 $$$(r + i - 1, c + j - 1)$$$ 与秘密文件的单元格 $$$(i, j)$$$ 对齐,即 $$$1 \leq i, j \leq 3$$$。
- 只有当秘密文件中相应的单元格有洞时,恶魔才能看到你的纸上的单元格的颜色。
- 如果可以通过孔看到奇数个黑色单元格,则结果网格的单元格 $$$(r, c)$$$ 上的值为 $$$1$$$,否则为 $$$0$$$。
如果结果网格仅包含值 $$$1$$$,则您赢得该回合。否则,恶魔会给你结果网格作为反馈,回合继续。
如果你已经花完了所有的金币,但仍然没有赢得所有回合,那么你将永远被困。逃离被诅咒的游戏!
互动
每轮都以奇数 $$$N$$$ ($$$3 \leq N \leq 33$$$) 开始,可以通过标准输入读取。
然后,对于您向恶魔提供的每个查询,您可以将 $$$N$$$ 行输出到标准输出。每 $$$N$$$ 行都由 $$$N$$$ 字符组成。第 $$$r$$$ 行的第 $$$c$$$ 字符代表论文中单元格 $$$(r, c)$$$ 的颜色。如果 $$$(r, c)$$$ 为黑色,则该字符应为 1;如果为白色,则该字符应为 0。
恶魔会回复一行由字符串组成的字符串,可以通过标准输入读取该字符串。
- 如果字符串正确,则您赢得当前回合,下一轮(如果存在)将立即开始。
- 如果字符串不正确,那么恶魔会给你多 $$$N - 2$$$ 行,这些行可以通过标准输入读取。每条 $$$N - 2$$$ 行均由 $$$N - 2$$$ 字符组成,表示二进制结果网格,如描述中所述。
恶魔们在每一轮开始前准备好秘密文件。换句话说,分级机不具有适应性。密纸上至少会有一个洞。
所有 $$$333$$$ 轮的查询总数不应超过 $$$999$$$。如果超过最大查询次数,则应使用 $$$0$$$ 终止程序,以接收“错误答案”的判决。如果不终止,判断结果将是未定义的,因为你的程序正在从关闭的流中读取。
不要忘记在每次输出后刷新输出缓冲区。在 C 中,您可以使用 fflush(stdout)。在 C++ 中,您可以使用 fflush(stdout) 或 cout «flush。在Java中,您可以对输出流使用flush方法,例如System.out.flush()。在Python中你可以使用stdout.flush()。
注意
示例交互#1
以下交互仅显示 $$$2$$$ 轮。实际的互动会一直持续到您赢得所有 $$$333$$$ 回合或者您的金币用完为止。
示例交互#1 的说明
对于第一轮,下图显示了恶魔如何在第一个和第二个查询的结果网格的单元格 $$$(1, 1)$$$ 中查找值。灰色方块代表密纸,圆圈代表孔。在第一个查询中,通过孔可以看到$$$4$$$黑色单元格,因此结果网格的单元格$$$(1, 1)$$$中的值为$$$0$$$。在第二个查询中,通过孔可以看到$$$5$$$黑色单元格,因此结果网格的单元格$$$(1, 1)$$$中的值为$$$1$$$。由于结果网格只有 1,第一轮结束。
对于第二轮,下图显示了恶魔如何在第一个查询的结果网格的单元格 $$$(2, 1)$$$ 中找到值。由于通过孔可以看到 $$$2$$$ 黑色单元格,因此单元格 $$$(2, 1)$$$ 中的值为 $$$0$$$。