P14001 [eJOI 2025] Prison

TL: 1s -> 2s

Alice 和 Bob 被不公正地判入一所最高戒备的监狱。现在他们必须策划越狱。为此，他们需要尽可能高效地通信（尤其是 Alice 需要每天向 Bob 发送信息）。然而他们无法见面，只能通过写在餐巾上的纸条交换信息。每天，Alice 想要向 Bob 发送一条新信息——一个介于 $0$ 与 $N-1$ 之间的数字。每次午餐时，Alice 会得到三张餐巾，并在每张餐巾上写一个 $0$ 到 $M-1$ 的数字（允许重复），然后把它们留在自己的座位上。接着，他们的敌人 Charly 会销毁其中一张餐巾，并把剩下两张的顺序打乱。最后，Bob 会找到仅存的两张餐巾并读取上面的数字。他必须**准确**解码出 Alice 最初想要发送的数字。餐巾上的空间有限，因此 $M$ 是固定的。不过，Alice 与 Bob 的目标是最大化通信吞吐量，所以他们可以自由选择尽可能大的 $N$。请通过为二人各自实现策略，尽力最大化 $N$ 的取值。 ### 实现细节 这是一个通信题，你的程序会以**两次独立执行**的方式运行（一次用于 Alice，一次用于 Bob），这两次执行无法共享数据，且除了下面描述的方式外不能相互通信。你需要实现三个函数： ```cpp int setup(int M); ``` 该函数会在 Alice 的执行开始时调用一次，在 Bob 的执行开始时也调用一次。它给出 $M$，必须返回你们希望使用的 $N$。两次对 `setup` 的调用必须返回**相同**的 $N$。 ```cpp std::vector encode(int A); ``` 这是 Alice 的策略实现。它会以待编码的数字 $A$（$0 \leq A < N$）作为参数被调用，必须返回三个数字 $W_1, W_2, W_3$（$0 \leq W_i < M$）来对 $A$ 进行编码。该函数总共会被调用 $T$ 次——每天一次（不同天的 $A$ 可能相同）。 ```cpp int decode(int X, int Y); ``` 这是 Bob 的策略实现。它会以 `encode` 返回的三个数字中的**两个**（顺序任意）作为参数被调用。它必须返回与 `encode` 接收的**相同**的值 $A$。该函数同样会被调用 $T$ 次——与 `encode` 的 $T$ 次调用一一对应；它们的顺序相同。所有对 `encode` 的调用都会**先于**所有对 `decode` 的调用完成。

无

无

### 示例 考虑以下示例，$T = 5$。这里的编码方案是：Alice 用三张相同的数字编码 $0$，用三张互不相同的数字编码 $1$。注意，Bob 可以仅根据 Alice 发送的三个数字中的任意两个，解码出原始数字。 | 执行端 | 函数调用 | 返回值 | | :-: | :-: | :-: | | Alice | setup(10) | 2 | | Bob | setup(10) | 2 | | Alice | encode(0) | {5, 5, 5} | | Alice | encode(1) | {8, 3, 7} | | Alice | encode(1) | {0, 3, 1} | | Alice | encode(0) | {7, 7, 7} | | Alice | encode(1) | {6, 2, 0} | | Bob | decode(5, 5) | 0 | | Bob | decode(8, 7) | 1 | | Bob | decode(3, 0) | 1 | | Bob | decode(7, 7) | 0 | | Bob | decode(2, 0) | 1 | ### 样例评测器 对于样例评测器，所有对 `encode` 与 `decode` 的调用都发生在你程序的**同一次执行**中。此外，`setup` 只会调用一次（与正式评测系统中每次执行各调用一次不同）。 输入仅包含一个整数——$M$。随后评测器会打印出你的 `setup` 返回的 $N$。接着它会进行 $T$ 轮：每一轮随机生成一个 $0$ 到 $N-1$ 的数字传给 `encode`，并随机从 `encode` 的三个返回值中选出两个（以及它们的顺序）传给 `decode`。若你的方案失败（解码错误），它会打印错误信息。 ### 约束 - $M \leq 4300$ - $T = 5000$ ### 评分 在某个子任务中，你所获得分数的比例 $S$ 取决于 `setup` 在该子任务任意测试上返回的最小 $N$，以及目标值 $N^*$（达到该值即可在该子任务拿满分）： - 若你的解在任一测试上失败，则 $S = 0$。 - 若 $N \geq N^*$，则 $S = 1.0$。 - 若 $N < N^*$，则 $$ S \;=\; \max\!\left(0.35 \cdot \max\!\left(\frac{\log N - 0.985 \log M}{\log N^* - 0.985 \log M},\, 0.0\right)^{0.3} \;+\; 0.65 \left(\frac{N}{N^*}\right)^{2.4},\; 0.01\right). $$ ### 子任务 | 子任务 | 分值 | $M$ | $N^*$ | |:-----:|:----:|:---:|:-----:| | 1 | 10 | 700 | 82017 | | 2 | 10 | 1100 | 202217 | | 3 | 10 | 1500 | 375751 | | 4 | 10 | 1900 | 602617 | | 5 | 10 | 2300 | 882817 | | 6 | 10 | 2700 | 1216351 | | 7 | 10 | 3100 | 1603217 | | 8 | 10 | 3500 | 2043417 | | 9 | 10 | 3900 | 2536951 | | 10 | 10 | 4300 | 3083817 | 翻译由 ChatGPT-5 完成。