← 返回题目列表

Codeforces · 2108/D

D. 数字栈中的针

中文机器翻译题面 查看原题

这是一个交互问题。

你在阁楼找到了数字 $$$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$$$。

该图显示了所有测试用例的数组。其值被请求的元素被标记为黄色。