Description

Alice 和 Bob 被不公正地判入一所最高戒备的监狱。现在他们必须策划越狱。为此，他们需要尽可能高效地通信（尤其是 Alice 需要每天向 Bob 发送信息）。然而他们无法见面，只能通过写在餐巾上的纸条交换信息。每天，Alice 想要向 Bob 发送一条新信息——一个介于 $0$ 与 $N-1$ 之间的数字。每次午餐时，Alice 会得到三张餐巾，并在每张餐巾上写一个 $0$ 到 $M-1$ 的数字（允许重复），然后把它们留在自己的座位上。接着，他们的敌人 Charly 会销毁其中一张餐巾，并把剩下两张的顺序打乱。最后，Bob 会找到仅存的两张餐巾并读取上面的数字。他必须准确解码出 Alice 最初想要发送的数字。餐巾上的空间有限，因此 $M$ 是固定的。不过，Alice 与 Bob 的目标是最大化通信吞吐量，所以他们可以自由选择尽可能大的 $N$。请通过为二人各自实现策略，尽力最大化 $N$ 的取值。

实现细节

这是一个通信题，你的程序会以两次独立执行的方式运行（一次用于 Alice，一次用于 Bob），这两次执行无法共享数据，且除了下面描述的方式外不能相互通信。你需要实现三个函数：

int setup(int M);

该函数会在 Alice 的执行开始时调用一次，在 Bob 的执行开始时也调用一次。它给出 $M$，必须返回你们希望使用的 $N$。两次对 setup 的调用必须返回相同的 $N$。

std::vector<int> encode(int A);

这是 Alice 的策略实现。它会以待编码的数字 $A$（$0 \leq A < N$）作为参数被调用，必须返回三个数字 $W_1, W_2, W_3$（$0 \leq W_i < M$）来对 $A$ 进行编码。该函数总共会被调用 $T$ 次——每天一次（不同天的 $A$ 可能相同）。

int decode(int X, int Y);

这是 Bob 的策略实现。它会以 encode 返回的三个数字中的两个（顺序任意）作为参数被调用。它必须返回与 encode 接收的相同的值 $A$。该函数同样会被调用 $T$ 次——与 encode 的 $T$ 次调用一一对应；它们的顺序相同。所有对 encode 的调用都会先于所有对 decode 的调用完成。

Hint

示例

考虑以下示例，$T = 5$。这里的编码方案是：Alice 用三张相同的数字编码 $0$，用三张互不相同的数字编码 $1$。注意，Bob 可以仅根据 Alice 发送的三个数字中的任意两个，解码出原始数字。

样例评测器

对于样例评测器，所有对 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).$$

子任务

翻译由 ChatGPT-5 完成。