这是一道交互题。
在一个遥远的国度中,人们使用着一套神秘的货币系统。在他们的货币系统中有 n 种不同的货币, 面值分别为 a1,a2,...,an,你可以假设每种货币的数量无限多。其中面值较小(即 ai≤103)的币种为硬币,记硬币的数量为 n1;而面值较大(即 ai>103)的币种为纸币,记纸币的数量为 n2。由于当地的特殊使用习惯,一些价格是可以通过组合这些货币表示出来的,而其他一些价格是不能被组合出来的。
现在你不知道这套货币系统的具体信息,包括 n 与 ai 的具体数值。但你可以通过向当地人询问一个价格 v 能否由这些货币组合出来。当然,你需要询问尽量少的次数确定 n 与 ai。
因为不同的 n 与 ai 可能可以达到相同的效果,所以你只需求出一种满足询问结果的答案。也就是说,对于所询范围内任意的 v,你的答案能否组合出 v 的结果应该与交互库的结果完全相同。
任务介绍
你需要实现一个函数 solve
,解出这套货币系统的 n 与 ai 的具体数值。
solve(type)
type
为该测试点的数据类型,具体见「数据规模和约定」。
在每个测试点中,交互库都会调用恰好一次 solve
函数。在该函数中你需要调用函数query
获取信息,调用函数answer
提交答案。
你可以调用函数 query
来询问一个价格能否由货币组合出来,但是这个函数的调用次数不能超过 limit 次。
query(v)
v
为你询问的价格,需要保证 0≤v≤1018;- 这个函数会返回 0 或 1 ,表示 v 是否能够被组合出来。
你需要调用函数 answer
来提交答案,这个函数必须恰好调用 1 次。
answer(n, a)
n
为你求出的答案的元素个数,需要保证 1≤n≤102 ;a
表示一个大小为 n 数组,其中数组的第 i 个位置的数值为 ai ,数组从 0 下标开始,需要保证 1≤ai≤109。
实现方法
你需要且只能提交一个源文件 currency.cpp
实现上述函数,且遵循下面的命名和接口。
源代码中需要包含头文件 currency.h
。
你需要实现的函数 solve
:
void solve(int type);
函数 query
的接口信息如下:
bool query(long long v);
函数 answer
的接口信息如下:
void answer(int n, int *a);
你可以将附加文件中的 currency.cpp
作为模板开始编写程序。
其他语言
C/C++ 以外的语言可以通过标准输入输出进行交互。
程序开始时,从标准输入读入一行,包含正整数 <type>
,表示该组测试数据的类型。
此后,需要调用 query()
时,向标准输出输出一行 Q <v>
并刷新输出缓冲(例如 Pascal 语言的 flush(output)
和 Java 语言的 System.out.flush()
,其他语言请参阅语言文档);此后从标准输入读入一行,包含一个整数 0 或 1 表示询问结果。
需要调用 answer()
时,向标准输出输出两行:第一行形如 A <n>
,第二行包含 n 个空格分隔的正整数 a1,a2,…,an。
所有输出同样需要满足上述限制。
子任务
对于 100% 的测试数据, 1≤n≤102,1≤ai≤109,交互库中的数据保证满足 n1,n2 的限制,但你提交的答案可以不满足该限制。
子任务 | 分值 | type= | limit= | n1 的规模 | n2 的规模 |
---|---|---|---|---|---|
1 | 6 | 1 | 1000 | =1 | =0 |
2 | 22 | 2 | 40 | ||
3 | 16 | 3 | 600 | =1 | |
4 | 12 | 4 | 1000 | ≥1 | =0 |
5 | 28 | 5 | 2200 | =1 | |
6 | 16 | 6 | 22000 | ≥1 |
如何测试你的程序(仅针对 C/C++ 语言)
g++ grader.cpp currency.cpp -o currency -O2
可执行文件将从标准输入读入数据,将结果输出到标准输出。
读入完成之后,交互库将调用 solve
函数。如果你调用 query
的次数超过 limit 次,或调用 answer
的次数小于或大于 1 次,则交互库会输出错误信息,并退出。如果传入 query
函数和 answer
函数的参数非法,那么交互库会输出详细的错误信息,并退出。
当正确调用answer
函数,solve
函数返回后,交互库会判断你提交的答案是否符合要求。如果答案正确,则会输出 Correct!
,否则会输出 Incorrect!
。
在编译命令中加入-DDEBUG
可以使交互库输出更多调试信息。
如果要使用自己的输入文件进行测试,请保证输入文件符合格式以下要求,否则不保证程序能正确运行。
第一行包含两个整数 type,limit,需要保证 type∈{1,2,3,4,5,6},0≤limit≤109。
第二行包含一个整数 n,需要保证 1≤n≤102。
第三行包含 n 个整数,其中第 i 个数为 ai,需要保证 1≤ai≤109 且 n1 与 n2 满足 type 类型的限制。
请注意最终测评使用的 currency.h
与下发的文件并不一致。