[AdditionalFile5177.zip](file://AdditionalFile5177.zip?type=additional_file)

#5177. 「POI2020 IOI Selection」Skarbiec

标签: 传统 | 时间限制: 21500 ms | 内存限制: 256 MiB |

题目描述

题目译自 XXVII Olimpiada Informatyczna – Eliminacje do IOI Skarbiec

这本该是一个平静的夜晚。Bajzek 坐在监控屏幕前，守卫着大楼。他在拜托克中央银行工作。这份工作不算有趣，但薪水不错，所以 Bajzek 并不抱怨。突然，他注意到一个摄像头的信号受到干扰。他决定去查看情况。当他到达现场时，看到一间房间里火焰正熊熊燃烧。

「必须检查宝库的情况……」Bajzek 心想，然后跑向楼上的宝库，那里存放着大量现金。「得把它们转移到安全的地方，」他自言自语，但很快意识到，他不能就这样把所有钞票打包带走……

宝库中的钞票被分成 $n$ 个堆栈。每个堆栈包含一定数量的钞票捆。然而，其中一个堆栈与众不同：它包含伪造的钞票，里面装有颜料，如果离开宝库就会爆炸。这是拜托克中央银行著名的安全措施之一。伪造钞票捆比真钞稍重：重量为 $101$ 克，而真钞捆为 $100$ 克。只有一个堆栈包含伪造钞票，且该堆栈中没有真钞。

宝库的角落里有一台非常精确的电子秤，可以测量任意一组钞票捆的重量。但遗憾的是，这台秤运行非常缓慢，而时间紧迫。

请编写一个与秤操作库交互的程序，通过最少的称重次数找出包含伪造钞票的堆栈。

交互方式

要使用库文件，程序开头需添加：

#include "skalib.h"

库文件提供了以下函数：

• initiuj()
  该函数提供宝库内容信息。返回一个包含 $n$ 个整数 $a_{1}, a_{2}, \ldots, a_{n}$ $(1 \leq n \leq 1000000, 1 \leq a_{i} \leq 10^{9})$ 的向量。数字 $a_{i}$ 表示第 $i$ 个堆栈中的钞票捆数量。

  • C++ 接口：vector<int> inicjuj();

• waz(p)
  该函数执行称重操作。其参数是一个包含恰好 $n$ 个整数 $p_{1}, p_{2}, \ldots, p_{n}$ $(0 \leq p_{i} \leq a_{i})$ 的向量。数字 $p_{i}$ 表示从第 $i$ 个堆栈中取出的钞票捆数量，Bajzek 将其放置在秤上。函数返回放置的钞票总重量（单位：克）。

  • C++ 接口：long long waz(const vector<int>& p);

• odpowiedz(k)
  该函数通知库文件，编号为 $k$ $(1 \leq k \leq n)$ 的堆栈包含伪造钞票。调用此函数会结束你的程序运行。

  • C++ 接口：void odpowiedz(int k);

你的程序不得从标准输入或文件读取任何数据，也不得向文件或标准输出写入任何内容。可以向标准错误输出（stderr）写入诊断信息，但请注意这会消耗宝贵的运行时间。

示例评测程序

示例代码及示例库文件可在「文件」中找到。库文件从标准输入读取以下格式的数据：

• 第一行：堆栈数量 $n$ 及伪造堆栈编号 $k$ $(1 \leq k \leq n)$，
• 第二行：堆栈大小 $a_{1}, \ldots, a_{n}$。

当调用 odpowiedz 函数时，库文件会输出信息，表明选手程序是否正确识别了伪造堆栈，以及执行的称重次数。特别地，示例库文件不检查执行的称重次数是否为最少。

编译时需确保 skalib.h 和 skalib.cpp 文件与解决方案位于同一目录下。编译命令如下：

g++ -O3 -static skalib.cpp ska.cpp -std=c++17

我们还提供了示例文件 makefile，可以通过以下命令从 ska.cpp 生成可执行文件 ska.e：

make

样例

下表展示了函数调用的样例序列。

上述程序流程是正确的。它使用了最少的 waz 函数调用次数，因此将获得满分。

附加样例

1. $n=3$，除一个堆栈外所有堆栈大小为 $1$；只需一次称重；
2. $n=10$，所有堆栈大小为 $1$；需要四次称重；
3. $n=1000$，堆栈大小不超过 $1000$；需要两次称重；
4. $n=1000000$，堆栈大小不超过 $1000$；需要十次称重。

数据范围与提示

令 $W$ 表示找到伪造堆栈所需的最小称重次数。详细子任务附加限制及分值如下表所示。

如果你的程序正确找到堆栈，且使用的 waz 函数调用次数不超过 $W$，则获得该测试 $100\%$ 的分数。如果调用次数为 $W+1$，则获得 $50\%$ 的分数；如果调用次数为 $W+2$，则获得 $25\%$ 的分数。如果程序未能找到伪造堆栈，或调用 waz 函数次数至少为 $W+3$，则获得 $0$ 分。