P15284 [IOI 2015] Scales 天平

**仅支持 C++ 交互。** 你不需要引入额外的头文件，但请在代码头部加入如下内容： ```cpp extern "C" { void init(int T); void orderCoins(); void answer(int W[]); int getMedian(int A, int B, int C); int getHeaviest(int A, int B, int C); int getLightest(int A, int B, int C); int getNextLightest(int A, int B, int C, int D); } ```

Amina 有 $6$ 枚重量互不相同的硬币（$1$ 到 $6$ 进行编号）。为了将这些硬币按重量排序，Amina 设计了一种新的天平。 传统的天平有两个秤盘，使用时在每个秤盘上放一枚硬币，即可称量出哪一枚硬币比较重。 Amina 的新天平比较复杂，它有 $4$ 个秤盘，分别记为 $A$，$B$，$C$，$D$。这个天平有 $4$ 种用法，每种用法回答一个关于硬币重量的问题。使用这个新天平时，秤盘 $A$，$B$，$C$ 上必须各放一枚硬币，注意：当使用新天平的第 $4$ 种用法时，秤盘 $D$ 上也必须放一枚硬币。 新天平的 $4$ 种用法分别回答下面的四个问题： 1. 秤盘 $A$，$B$，$C$ 上的硬币，哪个最重？ 2. 秤盘 $A$，$B$，$C$ 上的硬币，哪个最轻？ 3. 秤盘 $A$，$B$，$C$ 上的硬币，哪个既不是最轻也不是最重？ 4. 秤盘 $A$，$B$，$C$ 上的硬币里，比 $D$ 重的最轻的硬币是哪个？如果没有比 $D$ 重的硬币，那么 $A$，$B$，$C$ 上的硬币最轻的是哪个？ ### 任务 编写一个程序按硬币的重量对其排序，程序中可以使用 Amina 的新天平来比较硬币的重量。该程序需要解决若干个测试用例，每个测试用例对应一组新的 $6$ 个硬币的组合。 你的程序需要实现函数 `init` 和 `orderCoins`。每次运行你的程序，评测程序首先调用一次 `init` 函数（只调用一次），该函数告诉你评测用例的数目，在此函数中你可以初始化任意变量。接着，评测程序针对每组数据调用一次 `orderCoins()` 函数。 - `init(T)` - $T$：在这次运行中，你的程序需要求解的测试用例的数目。$T$ 是一个整数，取值范围是 $1,\dots ,18$。 - 该函数没有返回值。 - `orderCoins()` - 对于每组数据，该函数会恰好被调用一次。 - 该函数通过调用函数 `getHeaviest()`、`getLightest()`、`getMedian()`、`getNextLightest()` 来确定硬币的正确排序。 - 一旦知道了硬币的正确排序，该函数即可调用函数 `answer()`。 - 调用函数 `answer()` 后，本函数 `orderCoins()` 应该立即返回，且无返回值。 你的程序可以调用以下几个函数 (grader functions)： - `answer(W)` — 调用此函数来提交答案。 - $W$：长度为 $6$ 的数组，包含了硬币的正确排序，即 $W[0]$ 到 $W[5]$ 是按照硬币重量从小到大的顺序的硬币的编号（硬币的编号是从 $1$ 到 $6$ 的)。 - 对于每个测试用例，你的程序只能在函数 `orderCoins()` 中调一次 `answer(W)` 函数。 - `getHeaviest(A, B, C), getLightest(A, B, C), getMedian(A, B, C)` — 这 $3$ 个函数分别对应 Amina 的天平的第 $1$、$2$、$3$ 种用法。 - $A$、$B$、$C$: 分别表示放在秤盘 $A$、$B$、$C$ 上的硬币的编号。$A$、$B$、$C$ 是 $3$ 个互不相同的整数，每个整数的取值范围都是 $1$ 到 $6$。 - 每个函数均返回数字 $A$、$B$、$C$ 中的一个，表示符合条件的硬币的编号。例如，`getHeaviest(A, B, C)` 返回 $3$ 个硬币中最重的那个硬币的编号。 - `getNextLightest(A, B, C, D)` — 该函数对应 Amina 的天平的第 $4$ 种用法。 - $A, B, C, D$: 分别表示放在秤盘 $A$、$B$、$C$、$D$ 上的硬币的编号。$A$、$B$、$C$、$D$ 是 $4$ 个互不相同的整数，取值范围是 $1$ 到 $6$。 - 该函数返回 $A$、$B$、$C$ 中的一个数字: 表示 Amina 的天平第 $4$ 种用法选出的硬币的编号，即返回的硬币编号是秤盘 $A$、$B$、$C$ 上比 $D$ 上硬币重的硬币中最轻的那个硬币的编号，或者，如果 $A$、$B$、$C$ 上的硬币都轻于 $D$ 上的硬币，么返回的是秤盘 $A$、$B$、$C$ 中最轻的那个硬币的编号。 ### 评分标准 **为了适应洛谷的计分方式，本题的计分方式进行了一定修改。** 本题没有子任务。你的得分与你称量的次数（调用函数 `getLightest()`、`getHeaviest()`、`getMedian()`、`getNextLightest()` 的总次数）有关。 每次运行时，你的程序会针对多个测试数据运行多次。如果你的程序在任何一次运行中对任意一组数据给出的硬币排序结果不正确，那么你将会得到 $0$ 分，否则，按照下面的规则进行评分。 假设 $Q$ 是使用 Amina 的天平对任意的 $6$ 个硬币进行排序所需要称量的最小次数。为了让本题更具挑战性，这里不告知 $Q$ 的值。 考虑你程序的一次运行，设这次运行中所有 $T$ 个测试用例中最大的称量次数为 $Q+x$，$x$ 是非负整数。（对每个测试用例，如果你的称量次数比 $Q$ 少，那么 $x=0$。）那么，这次运行你的得分是 $\dfrac{100}{x/5+1}$，**向下取整保留到整数**。 特别的，如果你的程序在每次运行中对任意测试用例都最多称量 $Q$ 次，你将得到 $100$ 分。

### 样例测试程序 样例测试程序将从标准读入中先读入一个正整数 $T$ 表示数据组数。 接下来 $T$ 行，每行一个长度为 $6$ 的排列，表示硬币从轻到重排序后的编号。 例如，包含 $2$ 个测试用例（硬币按重量从小到大排序分别是 $1$ $2$ $3$ $4$ $5$ $6$ 和 $3$ $4$ $6$ $2$ $1$ $5$）输入数据格式如下： ``` 2 1 2 3 4 5 6 3 4 6 2 1 5 ```

样例测试程序输出作为 `answer()` 函数参数的数组。

### 样例 假设硬币按重量从小到大排的顺序是 $3$ $4$ $6$ $2$ $1$ $5$。 |返回值 |返回值|说明 | |:--------:|:-:|:--------:| |`getMedian(4,5,6)`|$6$|$6$ 号硬币的重量在 $4$、$5$、$6$ 号硬币中居中。| |`getHeaviest(3,1,2)`|$1$|$1$ 号硬币是 $1$、$2$、$3$ 号硬币中最重的。| |`getNextLightest(2,3,4,5)`|$3$|$2$、$3$、$4$ 号硬币都比 $5$ 号硬币轻，所以返回 $2$、$3$、$4$ 号硬币中最轻的，即 $3$ 号。| |`getNextLightest(1,6,3,4)`|$6$|$1$、$6$ 号硬币均比 $4$ 号硬币重，返回它们两个中最轻的那个，即返回 $6$。| |`getHeaviest(3,5,6)`|$5$|$5$ 号硬币是 $3$、$5$、$6$ 号硬币中最重的。| |`getMedian(1,5,6)`|$1$|$1$ 号硬币的重量在 $1$、$5$、$6$ 号硬币中居中。| |`getMedian(2,4,6)`|$6$|$6$ 号硬币的重量在 $2$、$4$、$6$ 中居中。| |`answer([3,4,6,2,1,5])`| |程序找到的正确的排序结果。|