T181615 「MCOI-09」Calculating Entropy

**本题为 IO 交互题。**

评测机有一个正整数 $n$。 你可以和评测机交互来猜到 $n$。当你交互 **正整 `uint64_t`** $x$，评测机会： - 如果 $n=x$，评测机回答 `0`，本次交互停止。 - 否则，如果 $n>x$，评测机回答 `-1`，否则回答 `1`。 请用至多 $f(n)$ 次交互使评测机回答 `0`，其中 $f(n)$ 在数据范围里给定。 #### 交互格式 本题有 $T$ 次交互。正整数 $T$ 由评测机在交互开始时给定。 对于每一次交互，选手程序和评测机会进行以下交互： 1. 选手程序应该给出对 $n$ 的一个猜测 $x$，并向标准输出输出 $x$，并冲缓冲区。 2. 如果 $x=n$，评测机回复 $0$，本次交互停止。 3. 否则，评测机按照上述方式回复 $1$ 或者 $-1$，并回到步骤 1。 注意，当你使用交互次数超过 $f(n)$，评测机将立即停止；选手程序如果继续等待输入可能会报错为 WA，TLE，UKE 等状态。

见【交互格式】。

见【交互格式】。

#### 样例 1 解释 以上输入为评测机向程序输的信息，输出为程序向评测机输的信息。 初始，评测机给定 $T=1$。 选手猜 $1$，评测机回复 $n>1$。 选手猜 $2$，评测机回复 $n=2$，交互停止。 以上交互用 $2$ 次交互猜到 $n$。 **本题采用捆绑测试。** - Subtask 1（1 pts）：$T=n=1$，$f(n)=200$ - Subtask 2（9 pts）：$f(n)=200$ - Subtask 3（20 pts）：$f(n)=2\lceil\log_2 n\rceil+15$ - Subtask 4（30 pts）：$f(n)=\lceil\log_2 n\rceil+15$ - Subtask 5（40 pts）：$f(n)=\lceil\log_2 n\rceil+9$ 对于 $100\%$ 的数据，$1\le T\le 30$，$1\le n