#CF1906C. 被诅咒的游戏
被诅咒的游戏
C. 被诅咒的游戏
时间限制:$1$ 秒
内存限制:$1024$ MB
你在仓库里发现了一个古董盒子,并决定把它打开。就在你打开盒子的瞬间,你被困进了一个与恶魔对弈的诅咒游戏中。这个游戏一共有 轮,你必须赢下全部轮次才能逃脱。恶魔还给了你 枚硬币,你可以在所有轮次中共同使用这些硬币。
注意,在本题中,如果一个网格的某个格子位于第 行第 列,则记为单元格 。
在每一轮开始之前,恶魔都会准备一张秘密纸片,可以表示为一个 的网格,行和列都从 到 编号。恶魔会在其中的一个或多个格子上打洞,但你并不知道具体哪些格子有洞。然后该轮开始,恶魔会给你一个奇数 ()。
在每一轮中,你可以向恶魔发出若干次询问,每次询问都需要花费一枚硬币。对于每次询问,你需要交给恶魔一张你自己的纸,可以表示为一个 的网格,行和列都从 到 编号。你可以把每个格子染成黑色或白色。
对于你的每次询问,恶魔会计算一个大小为 的二进制结果网格,行和列都从 到 编号。结果网格中单元格 的值按照如下方式确定。
恶魔会把秘密纸片盖在你的纸上,使得你纸上的单元格 与秘密纸片上的单元格 对齐,其中 。
只有当秘密纸片对应位置有洞时,恶魔才能看到你纸上的颜色。
如果恶魔透过这些洞看到的黑色格子数量是奇数,那么结果网格中的 填入 ;否则填入 。
如果某次询问得到的结果网格全部都是 ,那么你就赢下当前这一轮。否则,恶魔会把这个结果网格作为反馈告诉你,然后该轮继续进行。
如果你把所有硬币都花光了,却仍然没有赢下全部轮次,那么你就会被永远困住。请逃出这个被诅咒的游戏!
交互格式
每一轮开始时,输入中会给出一个奇数 ()。
之后,对于你向恶魔发出的每次询问,你需要向标准输出输出 行,每行包含 个字符。
第 行的第 个字符表示你纸上单元格 的颜色:
- 如果该格子染成黑色,则输出字符
1; - 如果该格子染成白色,则输出字符
0。
恶魔会通过标准输入回复一行字符串。
- 如果该字符串是
CORRECT,表示你赢下了当前这一轮,下一轮(如果存在)会立刻开始; - 如果该字符串是
INCORRECT,则恶魔接下来还会给出 行输入,每行包含 个字符,表示题面中定义的结果网格。
恶魔会在每一轮开始之前就先准备好秘密纸片。换句话说,评测程序不是自适应的。并且保证秘密纸片上至少有一个洞。
所有 轮中的询问总次数不能超过 。如果你超过了这个上限,你应当立即以返回值 终止程序,否则会得到 Wrong Answer。如果不终止,那么由于程序会继续从已经关闭的输入流读数据,评测结果将是未定义的。
不要忘记在每次输出后刷新输出缓冲区。
- 在 C 中可以使用
fflush(stdout); - 在 C++ 中可以使用
fflush(stdout)或cout << flush; - 在 Java 中可以对输出流调用
flush; - 在 Python 中可以使用
stdout.flush()。
说明
样例交互 只展示了其中 轮。真实交互会一直持续,直到你赢下全部 轮,或者硬币耗尽为止。
在样例交互 的第一轮中,题面配图展示了恶魔如何在第一次和第二次询问中计算结果网格的单元格 。灰色方块表示秘密纸片,圆圈表示洞。第一次询问时,恶魔能透过洞看到 个黑色格子,因此结果为 。第二次询问时,恶魔能看到 个黑色格子,因此结果为 。由于结果网格全部为 ,第一轮结束。
在样例交互 的第二轮中,题面配图展示了恶魔如何在第一次询问中计算结果网格的单元格 。由于恶魔能看到 个黑色格子,因此该位置结果为 。