这是一个交互问题。
你在阁楼找到了数字 $$$k$$$ 和 $$$n$$$,但丢失了两个数组 $$$A$$$ 和 $$$B$$$。
你还记得:
- $$$|A| + |B| = n$$$,数组的总长度为$$$n$$$。
- $$$|A| \geq k$$$ 和 $$$|B| \geq k$$$,每个数组的长度至少为$$$k$$$。
- 数组仅包含从 $$$1$$$ 到 $$$k$$$ 的数字。
- 如果从数组 $$$A$$$ 中取出任何 $$$k$$$ 连续元素,它们都会不同。另外,如果您从数组 $$$B$$$ 中取出任何 $$$k$$$ 连续元素,它们都会不同。
幸运的是,住在阁楼的一位善良的精灵发现了这些数组,并将它们连接成一个长度为 $$$n$$$ 的数组 $$$C$$$。也就是说,数组 $$$A$$$ 的元素首先写入数组 $$$C$$$,然后是数组 $$$B$$$ 的元素。
您可以向善心人士提出最多 $$$250$$$ 问题。每个问题都包含一个索引 $$$i$$$ ($$$1 \leq i \leq n$$$)。作为响应,您将收到连接数组 $$$C$$$ 的第 $$$i$$$ 个元素。
您需要找到数组 $$$A$$$ 和 $$$B$$$ 的长度,否则报告无法唯一确定它们。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 300$$$)。测试用例的描述如下。
每个测试用例的唯一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq k \leq 50$$$, $$$2 k \leq n \leq 10^{6}$$$)。
请注意,测试用例中 $$$n$$$ 的总和为 不限于.
互动
每个测试用例的交互都从读取整数 $$$n$$$ 开始。
那么您最多可以进行 $$$250$$$ 查询。
要进行查询,请输出格式为“的字符串”? x"(不带引号)($$$1 \leq x \leq n$$$)。每次查询后,读取一个整数——查询的答案。
如果您查询过多,您将收到以下判决: 错误答案.
要报告您的答案,请输出格式为“的字符串”!乙"(不带引号),其中 $$$a$$$ 和 $$$b$$$ 分别是您找到的数组 $$$A$$$ 和 $$$B$$$ 的长度。计算查询数时不计算答案。
如果无法唯一确定数组的长度,则输出“! -1“(不带引号)。请注意,如果您回答 $$$-1$$$,而存在最多 $$$250$$$ 查询的序列唯一确定数组的长度,您将得到 错误答案 判决。
保证存在数组 $$$A$$$ 和 $$$B$$$ 与语句不矛盾,交互器输出是正确的。
交互器是 不 自适应,这意味着答案在参与者提出查询之前就已知,并且不依赖于参与者提出的查询。
如果您的程序进行超过 $$$250$$$ 查询,您的程序应立即终止以接收判决 错误答案。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。
输出查询后,不要忘记输出换行符并刷新输出缓冲区。否则,您将收到“IL" (超出空闲限制)。要刷新缓冲区,请使用:
- fflush(标准输出) or cout.flush() 在 C++ 中;
- System.out.flush() 在 Java 中;
- 冲洗(输出) 帕斯卡;
- stdout.flush() 在 Python 中;
- 请参阅其他语言的文档。
黑客
对于此问题,黑客已被禁用。
示例
输入复制
6 5 2 1 2 2 18 4 2 4 1 1 4 3 1 10 5 9 3 3 3 2 12 4 1 3 1 3 1 3
输出复制
? 1 ? 2 ? 3 ! 2 3 ? 9 ? 13 ? 10 ? 14 ? 6 ! 9 9 ! -1 ! 5 5 ? 3 ? 6 ? 9 ! 6 3 ? 1 ? 2 ? 5 ? 6 ? 9 ? 10 ! -1
注意
考虑第一个例子。我们查询了 $$$5$$$ 中的前 $$$3$$$ 元素。现在我们知道数组 $$$C$$$ 看起来像 $$$[1, 2, 2, ?, ?]$$$。我们确信第三个元素不是来自数组 $$$A$$$ - 因为根据条件,数组 $$$A$$$ 中的任何 $$$k$$$ 连续元素(在我们的例子中 $$$k = 2$$$)都是不同的。因此,第三个元素肯定位于数组$$$B$$$中。这意味着数组$$$A$$$的长度是$$$2$$$,数组$$$B$$$的长度是$$$3$$$。
该图显示了所有测试用例的数组。其值被请求的元素被标记为黄色。