P14483 [集训队互测 2018] 神秘货币

试题来源：，向 LOJ 和出题人表示感谢。如果版权方并不希望试题出现在洛谷，可联系洛谷管理组撤下试题。

此题为交互式试题。 在一个遥远的国度中，人们使用着一套神秘的货币系统。在他们的货币系统中有 $n$ 种不同的货币， 面值分别为 $a_1, a_2, ... , a_n$，你可以假设每种货币的数量无限多。其中面值较小（即 $a_i \leq 10^3$）的币种为硬币，记硬币的数量为 $n_1$；而面值较大（即 $a_i > 10^3$）的币种为纸币，记纸币的数量为 $n_2$。由于当地的特殊使用习惯，一些价格是可以通过组合这些货币表示出来的，而其他一些价格是不能被组合出来的。 现在你不知道这套货币系统的具体信息，包括 $n$ 与 $a_i$ 的具体数值。但你可以通过向当地人询问一个价格 $v$ 能否由这些货币组合出来。当然，你需要询问尽量少的次数确定 $n$ 与 $a_i$。 因为不同的 $n$ 与 $a_i$ 可能可以达到相同的效果，所以你只需求出一种满足询问结果的答案。也就是说，对于所询范围内任意的 $v$，你的答案能否组合出 $v$ 的结果应该与交互库的结果完全相同。 ### 任务介绍 你需要实现一个函数 `solve`，解出这套货币系统的 $n$ 与 $a_i$ 的具体数值。 - `solve(type)` - `type` 为该测试点的数据类型，具体见「数据规模和约定」。 在每个测试点中，交互库都会调用恰好一次 `solve` 函数。在该函数中你需要调用函数`query`获取信息，调用函数`answer`提交答案。 你可以调用函数 `query` 来询问一个价格能否由货币组合出来，但是这个函数的调用次数不能超过 $limit$ 次。 - `query(v)` - `v` 为你询问的价格，需要保证 $0 \leq v \leq 10^{18}$； - 这个函数会返回 $0$ 或 $1$ ，表示 $v$ 是否能够被组合出来。 你需要调用函数 `answer` 来提交答案，这个函数必须恰好调用 $1$ 次。 - `answer(n, a)` - `n` 为你求出的答案的元素个数，需要保证 $1 \leq n \leq 10^2$ ； - `a` 表示一个大小为 $n$ 数组，其中数组的第 $i$ 个位置的数值为 $a_i$ ，数组从 $0$ 下标开始，需要保证 $1 \leq a_i \leq 10^9$。 ### 实现方法 你需要且只能提交一个源文件 `currency.cpp` 实现上述函数，且遵循下面的命名和接口。 你需要实现的函数 `solve`： ``` void solve(int type); ``` 函数 `query` 的接口信息如下： ``` bool query(long long v); ``` 函数 `answer` 的接口信息如下： ``` void answer(int n, int *a); ``` 你需要在代码开头声明函数 `bool query(long long v);` 和 `void answer(int n, int *a);`。 ### 如何测试你的程序（仅针对 C/C++ 语言） `g++ grader.cpp currency.cpp -o currency -O2` 可执行文件将从**标准输入**读入数据，将结果输出到**标准输出**。 读入完成之后，交互库将调用 `solve` 函数。如果你调用 `query` 的次数超过 $limit$ 次，或调用 `answer` 的次数小于或大于 $1$ 次，则交互库会输出错误信息，并退出。如果传入 `query` 函数和 `answer` 函数的参数非法，那么交互库会输出详细的错误信息，并退出。 当正确调用`answer`函数，`solve` 函数返回后，交互库会判断你提交的答案是否符合要求。如果答案正确，则会输出 `Correct!`，否则会输出 `Incorrect!`。 在编译命令中加入 `-DDEBUG` 可以使交互库输出更多调试信息。 请注意最终测评使用的 `currency.h` 与下发的文件并不一致。

如果要使用自己的输入文件进行测试，请保证输入文件符合格式以下要求，否则不保证程序能正确运行。 第一行包含两个整数 $type, limit$，需要保证 $type \in \{1, 2, 3, 4, 5, 6\}, 0 \leq limit \leq 10^9$。 第二行包含一个整数 $n$，需要保证 $1 \leq n \leq 10^2$。 第三行包含 $n$ 个整数，其中第 $i$ 个数为 $a_i$，需要保证 $1 \leq a_i \leq 10^9$ 且 $n_1$ 与 $n_2$ 满足 $type$ 类型的限制。

无

对于 $100 \%$ 的测试数据， $1 \leq n \leq 10^2, 1 \leq a_i \leq 10^9$，交互库中的数据保证满足 $n_1, n_2$ 的限制，但你提交的答案可以不满足该限制。 | 子任务 | 分值 | $ type = $ | $limit = $ | $n_1$ 的规模 | $n_2$ 的规模 | | :--: | :--: | :---------: | :----------: | :---------: | :---------: | | $1$ | $6$ | $1$ | $1000$ | $= 1$ | $= 0$ | | $2$ | $22$ | $2$ | $40$ | $= 1$ | $= 0$ | | $3$ | $16$ | $3$ | $600$ | $= 1$ | $= 1$ | | $4$ | $12$ | $4$ | $1000$ | $\geq 1$ | $= 0$ | | $5$ | $28$ | $5$ | $2200$ | $\geq 1$ | $= 1$ | | $6$ | $16$ | $6$ | $22000$ | $\geq 1$ | $\geq 1$ |