#20. 函数交互测试

函数交互测试

题目描述

这是一道交互测试题。

给定 nn 枚编号为 1n1 \sim n 的硬币,其中有 11 枚硬币较为特殊,每次你可以选择一枚硬币进行询问。对于正常的硬币询问时有 50%50\% 的概率返回 1150%50\% 的概率返回 00;对于特殊的硬币询问时有 40%40\% 的概率返回 1160%60\% 的概率返回 00。请你找出这枚特殊硬币。

由于这是交互测试题,所以对于交互数量没有严格限制,但你不应当进行 10510^5 以上次的询问。

你可以调用 coin.h 进行交互,具体地,交互命令有以下三种。

int getn() 返回一个不超过 100100 的整数,表示 nn。你应当在程序一开始调用此函数,并仅调用一次。

int query(int x) 询问第 xx 枚硬币,返回值见题目描述。

void submit(int x) 提交你的答案,即第 xx 枚硬币是特殊的。在此之后你不应当进行任何交互操作。

数据规模与约定

交互库请从 附件 下载,不保证其实现一定与评测时采用的交互库相同。

注意: 此题暂时仅支持 C++。