琳达喜欢时不时地改变她的头发颜色,如果她的男朋友阿奇能注意到以前的颜色和新颜色之间的差异,她会很高兴。当且仅当阿奇注意到差异时,阿奇总是评论琳达的头发颜色 - 所以琳达总是知道阿奇是否发现了差异。
市场上有一个新的染发剂系列,所有可用颜色均以$$$1$$$至$$$N$$$之间的整数编号,数值差异较小也意味着视觉差异较小。
Linda 假设这些系列应该存在一些关键色差 $$$C$$$ ($$$1 \le C \le N$$$),Archie 会注意到当前颜色 $$$\mathrm{color}_{\mathrm{new}}$$$ 和先前颜色 $$$\mathrm{color}_{\mathrm{prev}}$$$ 之间的色差,如果$$$\left|\mathrm{颜色}_{\mathrm{新}} - \mathrm{颜色}_{\mathrm{上一个}}\right| \ge C$$$ 则不会,如果 $$$\left|\mathrm{color}_{\mathrm{new}} - \mathrm{color}_{\mathrm{prev}}\right| < C$$$。
现在她已经购买了新系列的 $$$N$$$ 套染发剂 - 从 $$$1$$$ 到 $$$N$$$ 每种颜色各一套,并准备开始实验。琳达会定期改变头发的颜色,并观察阿奇的反应——无论他是否会注意到颜色的变化。由于为了获得正确的染料,每组都应完全使用,因此每种头发颜色只能获得一次。
在实验之前,Linda 使用的是不同系列的染料,该染料与新染料不兼容,因此为了实验的清晰度,Archie 对第一种使用的颜色的反应没有意义。
她的目标是在有限数量的染料中找到 $$$C$$$ 的精确值。编写一个程序,通过试验给定的 $$$N$$$ 颜色并观察阿奇对颜色变化的反应来找到 $$$C$$$ 的值。
互动
这是一项交互式任务。一开始,您会得到一个整数 $$$T$$$ ($$$1 \leq T \leq 100$$$),即测试中的案例数。
对于每个测试用例,输入首先包含一个整数 - $$$N$$$ 的值 ($$$1 < N \le 10^{18}$$$)。 $$$C$$$ 的值由评分系统保密。
然后你的程序应该以以下格式进行查询写入输出:“? $$$P$$$”,其中 $$$P$$$ 是一个整数 ($$$1 \le P \le N$$$) 表示使用的下一个颜色。对于每个查询,评分系统都会在输入的下一行给出答案。如果阿奇注意到最后两种颜色之间的色差,答案是 $$$1$$$,否则答案是 $$$0$$$。两个查询不应具有相同的 $$$P$$$ 值。
当您的程序确定 $$$C$$$ 时,它应该按以下格式输出其值:“= $$$C$$$”。评分系统不会响应此输出,并将继续进行下一个测试用例。
您的程序最多可以使用 64 个查询“?”对于每个测试用例,找到 $$$C$$$ 的正确值。
为了在程序和评分系统之间建立正确的通信,您应该在每次查询后刷新输出流。
$$$$$$\begin{array}{ll} \text{语言} & \text{命令} \\ \hline \text{C++} & \texttt{std::cout }\texttt{<}\texttt{<}\texttt{ std::endl;} \\ \text{Java} & \texttt{System.out.flush();} \\ \text{Python} & \texttt{sys.stdout.flush()} \end{array}$$$$$$ 刷新命令
请注意,std::endl 写入换行符并刷新流。
如果在通信过程中违反任务限制,即使在打印正确答案后也可能收到“输出不正确”结果。违反通信协议本身可能会导致“执行被杀死”的结果。
提交用户测试需要指定带有测试用例参数的输入文件。输入文件的格式是第一行中的“$$$T$$$”,然后对于每个 $$$T$$$ 情况,在单行上为“$$$N$$$ $$$C$$$”。
示例
输入 #1
1 7 1 1 0 0 1
输出 #1
? 2 ? 7 ? 4 ? 1 ? 5 = 4
注意
评分:
子任务:
1.(9分)$$$N \le 64$$$
2.(13 分)$$$N \le 125$$$
3.(21分)$$$N \le 1000$$$
4.(24分)$$$N \le 10^9$$$
5. (33 分) 没有进一步的限制。
对示例输入逐行的注释:
1. $$$N = 7$$$。
2. 第一个查询的答案没有意义(也可以是$$$0$$$)。
3. $$$C \leq 5$$$。
4. $$$3 < C \leq 5$$$。明智的做法是检查差异 $$$4$$$。然而,这不能在下一个查询中完成,因为 $$$4 + 4 = 8$$$ 和 $$$4 - 4 = 0$$$ 都超出了允许的区间 $$$1 \le P \le 7$$$。
5. $$$3 < C \leq 5$$$。
6. $$$3 < C \leq 4$$$。因此,$$$C = 4$$$。