【IOI2015】Scales - 题目 - Universal Online Judge

Amina有 $6$ 枚重量互不相同的硬币（$1$ 到 $6$ 进行编号）。为了将这些硬币按重量排序，Amina 设计了一种新的天平。

传统的天平有两个秤盘，使用时在每个秤盘上放一枚硬币，即可称量出哪一枚硬币比较重。

Amina 的新天平比较复杂，它有 4 个秤盘，分别记为 $A$，$B$，$C$，$D$。这个天平有 $4$ 种用法，每种用法回答一个关于硬币重量的问题。使用这个新天平时，秤盘 $A$，$B$，$C$上必须各放一枚硬币，注意：当使用新天平的第 $4$ 种用法时，秤盘 $D$ 上也必须放一枚硬币。

新天平的 $4$ 种用法分别回答下面的四个问题：

编写一个程序按硬币的重量对其排序，程序中可以使用 Amina 的新天平来比较硬币的重量。该程序需要解决若干组数据，每组数据对应一组新的 6 个硬币的组合。

你的程序需要实现函数 init 和 orderCoins。每次运行你的程序，评测程序首先调用一次 init 函数（只调用一次），该函数告诉你数据组数，在此函数中你可以初始化任意变量。接着，评测程序针对每组数据调用一次 orderCoins() 函数。

init(T)
- T：数据组数。
- 该函数不应该有返回值。
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分，否则，按照下面的规则进行评分。

设你的程序中，步数最多的一组数据超过了标准答案 $x$ 步，那么你将得到 $\frac{1}{x/5+1}$的分数（下取整）

假设硬币按重量从小到大排的顺序是 $3$ $4$ $6$ $2$ $1$ $5$

评测系统将从标准读入中先读入一个正整数 $T$ 表示数据组数。

接下来 $T$ 行，每行一个长度为 $6$ 的排列，表示硬币从轻到重排序后的编号。

$1 \leq T \leq 18$

你的得分是每个测试数据中得分最小的那个。

时间限制：$1\texttt{s}$

空间限制：$256\texttt{MB}$

Universal Online Judge