题目描述

这是一道交互测试题。

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

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

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

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

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

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

数据规模与约定

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

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