问题描述

有 $n$ 堆硬币，第 $i$（$0\le i<n$）堆硬币有 $a_i$ 枚。每一枚硬币的质量是 $5$ 克，但有一堆当中的所有硬币都是假币，假币的质量是每一枚 $6$ 克。除了这一堆外的所有硬币都是真币。

你有一个精确的称重仪器，在它上面放置任意枚硬币之后，它会返回这些硬币的质量之和。

你需要找到假币是哪一堆，且称重的次数尽可能少。

实现要求

你的程序应当包含如下的头文件：

• #include "coins.h"
  

你的程序不应包含 main 函数，而应当实现以下函数：

• int solve(std::vector<int> a);
  

  该函数接受大小为 $n$ 的数组 $a$，含义与题面中相同。该函数应当返回一个 $0$ 到 $n-1$ 中的整数，表示假币堆的编号。

你的程序可以调用以下函数：

• long long weigh(std::vector<int> p);
  

  该函数接受大小为 $n$ 的数组 $p$，其中 $0\le p_i\le a_i$，表示将第 $i$ 堆中的 $p_i$ 枚硬币放到称重仪器上。该函数返回所有放到仪器上的硬币的质量之和。称重完成后，所有硬币将会回到它本来所在的堆。

你的程序不应进行任何输入和输出操作。但是，作为特例，你可以向标准错误流（stderr）输出信息，但是注意这也会计算进你的运行时间。

样例

假设 $a=[1,2]$，假币堆的编号为 $0$。评分程序将会调用 solve([1, 2])。

示例解决方案将会调用 weigh([1, 0])，得到返回值 $6$。

示例解决方案找到了假币堆，于是返回其编号 $0$。

评分方式

在每个测试点中，solve 函数将会被调用恰好一次。如果你的程序没有正确运行，或是没有返回正确的答案，则得分为 $0$。

如果你的程序正确运行，且返回了正确的答案，令 $W$ 是如果使用最优策略，在最坏情况下确定假币堆需要的称重次数的最小值。令 $C$ 为你的程序调用 weigh 函数的次数。则你在该测试点的得分为：

你在一个子任务的得分是该子任务中每个测试点得分的最小值。

在正式的评分程序中，如果你调用 weigh 函数的次数不超过 $W+2$，则保证评分程序占用的时间不超过 1 秒，占用的空间不超过 256MiB。

数据约束

• $1\le n\le 10^6$
• $1\le a_i\le 10^9$（$0\le i<n$）

子任务的列表如下：

测试

下发文件中包含了如下内容：

• coins.h：你的程序需要包含的头文件。
• coins.cpp：本题解决方案的示例代码。
• grader.cpp：示例评分程序。
• coins1~3.in：样例输入。

你可以使用以下的命令编译示例评分程序（其中 coins.cpp 是你的解决方案）：

g++ -std=c++14 -O2 -o grader coins.cpp grader.cpp

编译好的评分程序将会从标准输入以如下的格式读入数据：

• 第一行两个整数 $n,k$，表示硬币的堆数和假币堆的编号。
• 第二行 $n$ 个整数 $a_0,a_1,\ldots,a_{n-1}$，表示每一堆硬币的枚数。

如果你的程序执行了不合法的操作，或是得到了错误的答案，评分程序会返回如下的错误：

• Wrong answer [1]：$p$ 的大小不为 $n$。
• Wrong answer [2]：$p_i$ 的范围不在 $0$ 到 $a_i$ 中。
• Wrong answer [3]：solve 的返回值不在 $0$ 到 $n-1$ 中。
• Wrong answer [4]：solve 返回了错误的硬币堆。

如果你的程序正确运行并返回了正确答案，则评分程序会告知你调用 weigh 函数的次数。

注意！示例评分程序和正式评分使用的评分程序不同：

• 示例程序并不会检查你的称重次数是否是最少的。

• 正式评分程序是适应性的，即假币堆并不是事先确定的，而是可以在交互过程中随时改变，只要与之前的所有称重结果一致。