QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100 Interactive

# 4783. 神秘货币

统计

这是一道交互题。

在一个遥远的国度中,人们使用着一套神秘的货币系统。在他们的货币系统中有 $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 实现上述函数,且遵循下面的命名和接口。

源代码中需要包含头文件 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$ 个空格分隔的正整数 $a_1, a_2, \ldots, a_n$。

所有输出同样需要满足上述限制。

子任务

对于 $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
3 16 3 600 $= 1$
4 12 4 1000 $\geq 1$ $= 0$
5 28 5 2200 $= 1$
6 16 6 22000 $\geq 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 \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$ 类型的限制。

请注意最终测评使用的 currency.h 与下发的文件并不一致。