#P15684. [ICPC 2023 Jakarta R] Cursed Game
[ICPC 2023 Jakarta R] Cursed Game
说明
你在仓库中发现了一个古老的盒子,并决定打开它。就在你打开盒子的那一刻,它把你拖入了一个诅咒游戏,你将与一个恶魔对抗。游戏共进行 轮,你必须赢得所有轮次才能逃脱。恶魔还给了你 枚硬币,你可以在所有轮次中使用。
请注意,在本问题中,将网格的单元格 定义为网格中第 行第 列的单元格。
在每一轮开始前,恶魔会准备一张秘密纸张,它可以表示为一个 行 列的网格,行和列都从 到 编号。恶魔会秘密地在其中一个或多个单元格上打洞,而你并不知道哪些单元格有洞。然后,该轮以恶魔给你一个奇数 ()开始。
在每一轮中,你可以向恶魔提出若干次询问,每次询问会花费你一枚硬币。对于每次询问,你可以给恶魔你的纸张,它可以表示为一个 行 列的网格,行和列都从 到 编号。每个单元格由你涂成黑色或白色。
对于你的每次询问,恶魔会计算一个二进制结果网格,它有 行和 列,行和列都从 到 编号。结果网格中单元格 的值按如下方式填充。
- 恶魔会将秘密纸张覆盖在你的纸张上,使得你的纸张的单元格 与秘密纸张的单元格 对齐,其中 。
- 只有当秘密纸张中对应的单元格有洞时,恶魔才能看到你纸张中该单元格的颜色。
- 结果网格中单元格 的值为 ,如果恶魔通过洞看到的黑色单元格数量为奇数;否则为 。
如果你赢得该轮,当且仅当结果网格中的所有值都是 。否则,恶魔会将结果网格作为反馈给你,该轮继续。
如果你花光了所有硬币仍未赢得所有轮次,那么你将永远被困住。请逃脱这个诅咒游戏!
交互过程
每一轮以一个可以通过标准输入读取的奇数 ()开始。
然后,对于你向恶魔提出的每次询问,你可以向标准输出输出 行。每行包含 个字符。第 行的第 个字符代表你纸张中单元格 的颜色。如果 被涂成黑色,字符应为 ;如果涂成白色,字符应为 。
恶魔将回复一行一个字符串,可以通过标准输入读取。
- 如果字符串是 CORRECT,那么你赢得了当前轮次,并且下一轮(如果存在)将立即开始。
- 如果字符串是 INCORRECT,那么恶魔将再给出 行,可以通过标准输入读取。这 行每行包含 个字符,代表题目描述中解释的二进制结果网格。
恶魔在每轮开始前准备秘密纸张。换句话说,评测程序是非自适应的。秘密纸张中至少有一个洞。
所有 轮的总询问次数不应超过 。如果你超过了最大询问次数,你应该终止你的程序并返回 以收到 Wrong Answer 的判定。如果你不终止,由于你的程序正在从已关闭的流中读取,评测结果将是未定义的。
不要忘记在每次输出后刷新输出缓冲区。在 C 语言中,你可以使用 fflush(stdout)。在 C++ 中,你可以使用 fflush(stdout) 或 cout << flush。在 Java 中,你可以对输出流使用 flush 方法,例如 System.out.flush()。在 Python 中,你可以使用 stdout.flush()。
提示
样例交互 #1
以下交互只展示了 轮。实际的交互会持续到你赢得所有 轮或用完硬币为止。
:::align{center}
:::
对样例交互 #1 的解释
对于第一轮,下图展示了恶魔如何为第一次和第二次询问找到结果网格中单元格 的值。灰色方块代表秘密纸张,圆圈代表洞。在第一次询问中,通过洞可以看到 个黑色单元格,因此结果网格中单元格 的值为 。在第二次询问中,通过洞可以看到 个黑色单元格,因此结果网格中单元格 的值为 。由于结果网格全为 1,第一轮结束。
:::align{center}
:::
对于第二轮,下图展示了恶魔如何为第一次询问找到结果网格中单元格 的值。由于通过洞可以看到 个黑色单元格,单元格 的值为 。
:::align{center}
:::
翻译由 DeepSeek V3 完成
京公网安备 11011102002149号