P15450 [IOI 2011] Parrots（通信题无法评测）

**本题暂时无法评测。**

Yanee 是一位鸟类爱好者。自从阅读了关于《鸟类载波 IP 协议》（IP over Avian Carriers, IPoAC）的文章后，她花费了大量时间训练一群聪明的鹦鹉，让它们长距离携带信息。 Yanee 的梦想是用她的鸟将一条消息 $M$ 发送到很远很远的地方。她的消息 $M$ 是一个长度为 $N$ 的整数序列，每个整数都在 $0$ 到 $255$ 之间（包括 $0$ 和 $255$）。Yanee 养了 $K$ 只受过特殊训练的鹦鹉。所有鹦鹉看起来都一样，Yanee 无法区分它们。每只鸟能记住一个介于 $0$ 和 $R$ 之间（包括 $0$ 和 $R$）的整数。 起初，她尝试了一个简单的方案：为了发送消息，Yanee 小心翼翼地将鸟一只一只地放出笼子。在每只鸟飞向天空之前，她按顺序教给它消息序列中的一个数字。不幸的是，这个方案失败了。最终，所有的鸟确实都到达了目的地，但它们到达的顺序不一定与离开的顺序相同。用这个方案，Yanee 可以恢复她发送的所有数字，但无法将它们按正确顺序排列。 为了实现她的梦想，Yanee 需要一个更好的方案，为此她需要你的帮助。给定一条消息 $M$，她计划像以前一样将鸟一只一只地放出。她需要你编写一个程序，该程序将执行两个独立的操作： - 首先，你的程序应能读取消息 $M$，并将其转换为一个长度至多为 $K$、元素介于 $0$ 和 $R$ 之间的整数序列，她将把这些数教给鹦鹉。 - 其次，你的程序应能读取当鹦鹉到达目的地后收到的、介于 $0$ 和 $R$ 之间的整数列表，并将其转换回原始消息 $M$。 你可以假设所有鹦鹉总能到达目的地，并且每只鹦鹉都记得分配给它的数字。Yanee 再次提醒你，鹦鹉可能以任意顺序到达。注意 Yanee 只有 $K$ 只鹦鹉，因此你生成的介于 $0$ 和 $R$ 之间的整数序列必须至多包含 $K$ 个整数。 ### 交互细节 请编写两个独立的过程。一个将由发送方（编码器）使用，另一个将由接收方（解码器）使用。 整个过程如下图所示。  你要编写的两个过程是： - 过程 `encode(N,M)`，它接受以下参数： - $N$ - 消息的长度。 - $M$ - 一个一维数组，包含 $N$ 个整数，表示消息。你可以假设对于 $0 \le i < N$，有 $0 \le M[i] \le 255$。 - 此过程必须将消息 $M$ 编码成一个介于 $0$ 和 $R$ 之间（包括 $0$ 和 $R$）的整数序列，该序列将用鹦鹉发送。为了报告这个序列，你的 `encode` 过程必须为每个你想给某只鸟的整数 $a$ 调用一次过程 `send(a)`。 - 过程 `decode(N,L,X)`，它接受以下参数： - N - 原始消息的长度。 - L - 接收到的消息的长度（被发送的鹦鹉的数量）。 - X - 一个一维数组，包含 $L$ 个整数，表示接收到的数字。数字 $X[i]$（$0 \le i < L$）恰好是你的 `encode` 过程产生的那些数字，但可能被重新排列成了不同的顺序。 - 此过程必须恢复原始消息。为了报告消息，你的 `decode` 过程必须为解码后消息中的每个整数 $b$ 按正确顺序调用一次过程 `output(b)`。 请注意，$R$ 和 $K$ 不作为输入参数给出——请参阅下面的子任务描述。 为了正确解决给定的子任务，你的过程必须满足以下条件： - 你的 `encode` 过程发送的所有整数必须在子任务指定的范围内。 - 你的 `encode` 过程调用 `send` 过程的次数不得超过子任务中指定的限制 $K$。请注意 $K$ 取决于消息的长度。 - `decode` 过程必须正确恢复原始消息 $M$，并恰好调用 `output(b)` 过程 $N$ 次，其中 $b$ 分别等于 $M[0], M[1], \ldots, M[N-1]$。 在最后一个子任务中，你的得分根据编码后消息与原始消息的长度之比而变化。 ### 交互示例 考虑 $N = 3$，且 $M=\{10,30,20\}$ 的情况。 过程 `encode(N,M)` 可能使用某种奇怪的方法将消息编码为数字序列 $(7, 3, 2, 70, 15, 20, 3)$。为了报告这个序列，它应该如下调用 `send` 过程： ```plain send(7) send(3) send(2) send(70) send(15) send(20) send(3) ``` 一旦所有鹦鹉到达目的地，假设我们得到以下转录的数字列表：$(3, 20, 70, 15, 2, 3, 7)$。随后将以 $N=3$，$L=7$，$X=\{3,20,70,15,2,3,7\}$ 调用过程 `decode`。 过程 `decode` 必须产生原始消息 $(10, 30, 20)$。它通过如下调用 `output` 过程来报告结果。 ```plain output(10) output(30) output(20) ```

无

无

### 数据范围 #### 子任务 1（17 分） - $N = 8$，且数组 $M$ 中的每个整数要么是 $0$ 要么是 $1$。 - 每个编码后的整数必须在 $0$ 到 $R=65535$ 的范围内（包括 $0$ 和 $65535$）。 - 你可以调用 `send` 过程的次数最多为 $K=10\times N$。 #### 子任务 2（17 分） - $1 \le N \le 16$。 - 每个编码后的整数必须在 $0$ 到 $R=65535$ 的范围内（包括 $0$ 和 $65535$）。 - 你可以调用 `send` 过程的次数最多为 $K=10\times N$。 #### 子任务 3（18 分） - $1 \le N \le 16$。 - 每个编码后的整数必须在 $0$ 到 $R=255$ 的范围内（包括 $0$ 和 $255$）。 - 你可以调用 `send` 过程的次数最多为 $K=10\times N$。 #### 子任务 4（29 分） - $1 \le N \le 32$。 - 每个编码后的整数必须在 $0$ 到 $R=255$ 的范围内（包括 $0$ 和 $255$）。 - 你可以调用 `send` 过程的次数最多为 $K=10\times N$。 #### 子任务 5（最多 19 分） - $16 \le N \le 64$。 - 每个编码后的整数必须在 $0$ 到 $R=255$ 的范围内（包括 $0$ 和 $255$）。 - 你可以调用 `send` 过程的次数最多为 $K=15\times N$。 - **重要提示：** 此子任务的得分取决于编码后消息的长度与原始消息长度之比。 - 对于此子任务中的给定测试点 $t$，设 $P_t=L_t/N_t$ 为编码后消息长度 $L_t$ 与原始消息长度 $N_t$ 的比值。设 $P$ 为所有 $P_t$ 的最大值。你在此子任务中的得分将根据以下规则确定： - 如果 $P \le 5$，你将获得满分 $19$ 分。 - 如果 $5 < P \le 6$，你将获得 $18$ 分。 - 如果 $6 < P \le 7$，你将获得 $17$ 分。 - 如果 $7 < P \le 15$，你的得分为 $1 + 2 \times (15 - P)$，向下取整到最接近的整数。 - 如果 $P > 15$ 或你的任何输出不正确，你的得分为 $0$。 - **重要提示：** 任何能有效解决子任务 1 到 4 的方案也能解决所有前面的子任务。然而，由于 $K$ 的上限更大，能有效解决子任务 5 的方案可能无法解决子任务 1 到 4。使用同一个方案解决所有子任务是可能的。