{"problem":{"name":"[IOI 2022] 囚徒挑战","description":{"content":"一个监狱里关着 $500$ 名囚徒。 有一天，监狱长给了他们一个重获自由的机会。 他把装钱的两个袋子 A 和 B 放在一个房间里。 每个袋子装有若干枚硬币，数量的范围在 $1$ 到 $N$ 之间（包含 $1$ 和 $N$）。 两个袋子里硬币的数量**不同**。 监狱长给囚徒们提出了挑战，目标是指出硬币数量较少的那个袋子。 房间里除了袋子还有一块白板。 任意时刻白板上写着一个数，一开始写的是 $0","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":2097152},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8491"},"statements":[{"statement_type":"Markdown","content":"一个监狱里关着 $500$ 名囚徒。\n有一天，监狱长给了他们一个重获自由的机会。\n他把装钱的两个袋子 A 和 B 放在一个房间里。\n每个袋子装有若干枚硬币，数量的范围在 $1$ 到 $N$ 之间（包含 $1$ 和 $N$）。\n两个袋子里硬币的数量**不同**。\n监狱长给囚徒们提出了挑战，目标是指出硬币数量较少的那个袋子。\n\n房间里除了袋子还有一块白板。\n任意时刻白板上写着一个数，一开始写的是 $0$。\n\n监狱长让囚徒一个接一个地进入房间。\n每个进入房间的囚徒不知道他之前进入过房间的囚徒有多少人，也不知道是哪些人。\n每次一个囚徒进入房间时，他看一眼白板上目前写的这个数。\n看完之后，他必须在袋子 A 和 B 之间做出选择。\n接着，他**检查**自己选的那个袋子，知道了里面有多少枚硬币。\n然后，这名囚徒必须选择做以下两种**行动**之一：\n\n* 将白板上的数改写成一个非负整数，并离开房间。\n注意他可以改变成新的数，也可以保留当前的数。\n然后挑战继续进行（除非所有 $500$ 名囚徒都已经进过房间）。\n* 指出硬币数量较少的那个袋子。这会立即结束挑战。\n\n对于已经进过房间的囚徒，监狱长不会让他再次进入房间。\n\n如果某个囚徒正确地指出硬币较少的袋子，则囚徒们获得挑战的胜利。\n如果指出的袋子不正确，或者所有 $500$ 人进过房间之后还没有人尝试指出硬币较少的袋子，则囚徒们失败。\n\n挑战开始之前，囚徒们集合在监狱大厅商量应对挑战的共同**策略**，分以下三个步骤：\n* 他们挑选一个非负整数 $x$，作为他们可能会写在白板上的最大的数。\n* 他们决定对任意一个数 $i$ ($0 \\le i \\le x$)，如果某个囚徒进入房间后看到白板上写着数 $i$，那么他应该去检查哪个袋子。\n* 他们决定当某个囚徒得知选中的袋子里的硬币数量后要采取的行动。具体来说，对任意写在白板上的数 $i$ ($0 \\le i \\le x$) 和检查选中的袋子里的硬币数量 $j$ ($1 \\le j \\le N$)，他们要决定做出以下两种行动之一：\n  - 白板上应该要写一个 $0$ 到 $x$ 之间（包含 $0$ 和 $x$）的什么数；\n  - 指出哪个袋子是硬币较少的。\n\n如果赢得挑战，监狱长会在囚徒们继续服刑 $x$ 天后释放他们。\n\n你的任务是提出能够确保囚徒们赢得挑战的策略（不管袋子 A 和 B 中的硬币数量是多少）。\n你的得分取决于 $x$ 的值（详见子任务一节）。\n\n## Input\n\n你要实现以下函数：\n\n```go\nint[][] devise_strategy(int N)\n```\n\n- $N$：每个袋子里硬币最多可能的数量。\n- 该函数需要返回一个数组 $s$，它的每个元素是长度为 $N + 1$ 的整数数组，表示你给出的策略。$x$ 的值是数组 $s$ 的长度减一。对满足 $0 \\le i \\le x$ 的每个 $i$，数组 $s_i$ 表示囚徒在进入房间看到白板上写着数 $i$ 时要做的事情：\n  1. 如果囚徒应该检查袋子 A，则 $s_{i, 0}$ 的值是 $0$；如果囚徒应该检查袋子 B，则该值是 $1$。\n  2. 令 $j$ 为所选袋子中的硬币数量，囚徒应该进行以下行动：\n     - 如果 $s_{i, j}$ 的值是 $-1$，则囚徒应该指出袋子 A 是硬币较少的袋子。\n     - 如果 $s_{i, j}$ 的值是 $-2$，则囚徒应该指出袋子 B 是硬币较少的袋子。\n     - 如果 $s_{i, j}$ 的值是非负整数，则囚徒应该把这个数写到白板上。注意 $s_{i, j}$ 至多只能是 $x$。\n- 该函数恰好被调用一次。\n\n## Output\n\n考虑以下调⽤：\n\n```go\ndevise_strategy(3)\n```\n\n令 $v$ 表示囚徒进入房间时看到白板上写着的数。以下是一种正确的策略：\n\n- 如果 $v = 0$（也包括开始时的数），则检查袋子 A。\n  - 如果它装了 $1$ 个硬币，则指出袋子 A 是硬币较少的袋子。\n  - 如果它装了 $3$ 个硬币，则指出袋子 B 是硬币较少的袋子。\n  - 如果它装了 $2$ 个硬币，则在白板上写上 $1$（覆盖之前的 $0$）。\n- 如果 $v = 1$，则检查袋子 B。\n  - 如果它装了 $1$ 个硬币，则指出袋子 B 是硬币较少的袋子。\n  - 如果它装了 $3$ 个硬币，则指出袋子 A 是硬币较少的袋子。\n  - 如果它装了 $2$ 个硬币，则在白板上写上 $0$（覆盖之前的 $1$）。注意，这种情况其实不可能发生，因为此时两个袋子都装有 $2$ 枚硬币，是不允许的。\n\n要产生以上策略，函数应该返回 `[[0, -1, 1, -2], [1, -2, 0, -1]]`。\n返回的数组长度是 $2$，此时 $x$ 的值是 $2 - 1 = 1$。\n\n[samples]\n\n## Background\n\n### 由于技术限制，请不要使用 C++ 14 (GCC 9) 提交本题。\n\n这是一道交互题，你只需要实现代码中要求的函数。\n\n你的代码不需要引用任何额外的头文件，也不需要实现 main 函数。\n\n## Note\n\n### 约束条件\n\n- $2 \\leq N \\leq 5000$。\n\n### 子任务\n\n1. （5 分）$N \\le 500$，$x$ 的值不能超过 $500$。\n1. （5 分）$N \\le 500$，$x$ 的值不能超过 $70$。\n1. （90分）$x$ 的值不能超过 $60$。\n\n对于任何测试用例，如果 `devise_strategy` 返回的数组是不合法的，则你在该子任务上的得分为 $0$。\n\n子任务 3 有部分分。\n令 $m$ 为该子任务中所有测试用例返回数组对应的 $x$ 的最大值，你的得分将根据下表计算：\n\n| 条件 | 得分 |\n| :-: | :-: |\n| $40 \\leq m \\leq 60$ | $20$ |\n| $26 \\leq m \\leq 39$ | $25 + 1.5 \\times (40 − m)$ |\n| $m = 25$ | $50$ |\n| $m = 24$ | $55$ |\n| $m = 23$ | $62$ |\n| $m = 22$ | $70$ |\n| $m = 21$ | $80$ |\n| $m \\leq 20$ | $90$ |\n\n### 评测程序示例\n\n评测程序示例按以下格式读取输入：\n\n* 第 $1$ 行：$N$\n* 第 $2 + k$ 行 ($0 \\le k$)：$A_k \\; B_k$\n* 最后一行：$-1$\n\n除第一行和最后一行外，每行表示一个场景。\n将第 $2 + k$ 行对应的场景称为场景 $k$。\n场景 $k$ 中，袋子 A 装有 $A[k]$ 枚硬币，袋子 B 装有 $B[k]$ 枚硬币。\n\n评测程序示例首先调用 `devise_strategy(N)`。\n$x$ 的值是返回数组的长度减一。\n如果评测程序示例检测到 `devise_strategy` 返回的数组不符合实现细节中描述的约束，它会打印如下错误信息并退出：\n\n* `s is an empty array`：$s$ 是空的数组（表示不合法的策略）。\n* `s[i] contains incorrect length`：存在一个下标 $i$ ($0 \\le i \\le x$) 满足 $s_i$ 的长度不是 $N + 1$。\n* `First element of s[i] is non-binary`：存在一个下标 $i$ ($0 \\le i \\le x$) 满足 $s_{i,0}$ 既不是 $0$，也不是$1$。\n* `s[i][j] contains incorrect value`：存在下标 $i, j$ ($0 \\le i \\le x, 1 \\le j \\le N$) 满足 $s_{i, j}$ 的值不在 $-2$ 和 $x$ 之间。\n\n否则，评测程序示例产生两项输出内容。\n\n首先，评测程序示例以如下格式打印你的策略的输出：\n\n* 第 $1 + k$ 行 ($0 \\le k$)：场景 $k$ 下你的策略的输出。\n如果用该策略导致某个囚徒指出袋子 A 是硬币较少的，则输出字符 `A`。\n如果用该策略导致某个囚徒指出袋子 B 是硬币较少的，则输出字符 `B`。\n如果用该策略后没有囚徒指出哪个袋子的硬币较少，则输出字符 `X`。\n\n其次，评测程序示例以如下格式在当前目录下写一个文件 `log.txt`：\n\n* 第 $1 + k$ 行 ($0 \\le k$)：$w_{k,0} \\; w_{k,1} \\; \\ldots$\n\n第 $1 + k$ 行的序列对应于场景 $k$，描述了写在白板上的数。\n具体来说，$w[k][l]$ 是第 $l + 1$ 个囚徒进入房间后写的数。\n\n### 约定\n\n题面在给出函数接口时，会使用一般性的类型名称 `void`、`int`、`int64`、`int[]`（数组）和 `int[][]`（数组的数组）。\n\n在 C++ 中，评测程序会采用适当的数据类型或实现，如下表所示：\n\n| `void ` | `int` | `int64`     | `int[]`            |\n| ------- | ----- | ----------- | ------------------ |\n| `void ` | `int` | `long long` | `std::vector<int>` |\n\n| `int[][]`                       | 数组 `a` 的长度 |\n| ------------------------------- | ------------------- |\n| `std::vector<std::vector<int>>` | `a.size()`          |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8491","tags":["2022","IOI","交互题","Special Judge","进制","构造","Ad-hoc"],"sample_group":[],"created_at":"2026-03-03 11:09:25"}}