你,一个被龙摧毁的法师,决心用魔法 AOE 追踪器追捕它。不过好像是被玩弄了……
这是一个交互问题。
有一个隐藏的二进制数组 $$$a$$$,长度为 $$$n$$$($$$\mathbf{n}$$$ 是 2 的幂)和一个隐藏的整数 $$$k\ (2 \le k \le n - 1)$$$。数组 $$$a$$$ 恰好包含一个 1(所有其他元素均为 0)。对于两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$),定义范围和 $$$s(l, r) = a_l + a_{l+1} + \cdots + a_r$$$。
你有一个神奇的装置,它接受范围并返回范围总和,但当范围的长度至少为 $$$k$$$ 时,它会返回相反的结果。正式地,在一个查询中,您可以给它一对整数 $$$[l, r]$$$,其中 $$$1 \le l \le r \le n$$$,它将根据以下规则返回 $$$0$$$ 或 $$$1$$$:
- 如果 $$$r - l + 1 < k$$$,它将返回 $$$s(l, r)$$$。
- 如果 $$$r - l + 1 \ge k$$$,它将返回 $$$1 - s(l, r)$$$。
使用最多 $$$33$$$ 查询查找 $$$k$$$。
该设备不具有自适应性。这意味着隐藏的$$$a$$$和$$$k$$$在交互之前是固定的,在交互过程中不会改变。
互动
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个正整数 $$$n$$$ ($$$4 \le n \le 2^{30}$$$) — 隐藏数组的长度。保证 $$$\mathbf{n}$$$ 是 2 的幂;也就是说,对于某个非负整数 $$$m$$$,$$$n = 2^m$$$。
您可以通过以下方式进行查询 - 打印一行“$$$\mathtt{?}\,l\,r$$$”,其中 $$$1 \le l \le r \le n$$$。之后,读取单个整数:$$$0$$$ 或 $$$1$$$,如语句中所述。
如果要打印答案$$$k$$$,请输出“$$$\mathtt{!}\,k$$$”。然后,继续与下一个测试用例进行交互。
打印答案不计入查询次数。
打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,您将得到超出空闲限制的判决。
如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,则您的解决方案必须立即退出。这意味着您的解决方案将由于无效查询或任何其他错误而收到错误答案。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。
黑客
黑客的格式应如下:第一行应包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。应遵循测试用例的描述。
每个测试用例的第一行也是唯一一行应包含三个整数 $$$n$$$、$$$p$$$ 和 $$$k$$$ ($$$4 \le n \le 2^{30}$$$, $$$1 \le p \le n$$$, $$$2 \le k \le n - 1$$$) — 隐藏数组 $$$a$$$ 的长度, $$$a$$$ 中唯一 1 的位置,以及隐藏的 $$$k$$$。 $$$n$$$ 必须是 $$$2$$$ 的幂。
示例
输入 #1
2 8 0 0 1 0 4 1 0
输出 #1
? 3 5 ? 1 8 ? 4 8 ? 3 8 ! 6 ? 3 3 ? 3 4 ! 2
注意
在第一个测试用例中,$$$k = 6$$$ 并且隐藏数组中的 1 位于索引 6 处,因此 $$$a = [0, 0, 0, 0, 0, 1, 0, 0]$$$。
- 对于查询 3 5,由于 $$$5-3+1 = 3 < k$$$,设备正确回答。由于 6 不包含在 $$$[3, 5]$$$ 范围内,因此设备回答 $$$0$$$。
- 对于查询 1 8,由于 $$$8 - 1 + 1 = 8 \ge k$$$,设备错误地回答 $$$0$$$。
- 对于查询 4 8,由于 $$$8 - 4 + 1 = 5 < k$$$,设备正确回答 $$$1$$$。
- 对于查询 3 8,由于 $$$8 - 3 + 1 = 6 \ge k$$$,设备错误地回答 $$$0$$$。
在第二个测试用例中,$$$k = 2$$$ 并且隐藏数组中的 1 位于索引 3 处,因此 $$$a = [0, 0, 1, 0]$$$。
请注意,示例解决方案可能没有足够的信息来确定上面的$$$k$$$;这只是一个例子。