这是一个交互问题。
您将获得一个包含 $$$n$$$ 行和 $$$m$$$ 列的网格。坐标 $$$(x, y)$$$ 表示网格上的单元格,其中 $$$x$$$ ($$$1 \leq x \leq n$$$) 是从顶部计数的行号,$$$y$$$ ($$$1 \leq y \leq m$$$) 是从左侧计数的列号。保证网格中不同单元格处恰好有 $$$2$$$ 地雷,表示为 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$。您最多可以向交互者进行 $$$4$$$ 查询,在这些查询之后,您需要提供其中一个地雷的位置。
在每个查询中,您可以选择任何网格单元格 $$$(x, y)$$$,作为回报,您将收到从两个地雷到所选单元格的最小曼哈顿距离,即,您将收到值 $$$\min(|x-x_1|+|y-y_1|, |x-x_2|+|y-y_2|)$$$。
您的任务是在进行查询后确定其中一个地雷的位置。
输入
每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 3 \cdot 10^{3}$$$) — 测试用例的数量。
每个测试用例的唯一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 10^{8}$$$, $$$2 \leq m \leq 10^{8}$$$) — 行数和列数。
互动
对于每个测试用例,交互从读取 $$$n$$$ 和 $$$m$$$ 开始。
那么您最多可以通过以下方式进行 $$$4$$$ 查询:
"? x y" ($$$1 \leq x \leq n$$$ 和 $$$1 \leq y \leq m$$$)
在每一个之后,您应该读取一个整数 $$$d$$$,它等于 $$$\min(|x-x_1|+|y-y_1|, |x-x_2|+|y-y_2|)$$$。
当您找到任一地雷的位置时,打印一行“! x y”(不带引号),代表其中一个地雷的行和列。输出答案不算作查询。
打印答案后,您的程序必须继续解决剩余的测试用例,或者如果所有测试用例都已解决则退出。
此问题的交互器不具有自适应性:地雷单元在进行任何查询之前就已固定。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客:
要进行破解,请使用以下格式:
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 3 \cdot 10^{3}$$$) — 测试用例的数量。
每个测试用例的描述应由三行组成。
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 10^{8}$$$, $$$2 \leq m \leq 10^{8}$$$) — 行数和列数。
第二行包含第一个矿井的坐标 $$$x_1$$$ 和 $$$y_1$$$($$$1 \leq x_1 \leq n$$$, $$$1 \leq y_1 \leq m$$$)。
第三行包含第二个矿井的坐标 $$$x_2$$$ 和 $$$y_2$$$($$$1 \leq x_2 \leq n$$$, $$$1 \leq y_2 \leq m$$$)。
地雷应该位于不同的位置。
示例
输入 #1
2 4 4 3 2 2 0 5 5 1 2 3
输出 #1
? 1 1 ? 1 4 ? 4 1 ? 2 3 ! 2 3 ? 5 5 ? 2 2 ? 3 3 ! 1 1
注意
在第一个测试用例中,我们首先查询左上角$$$(1, 1)$$$,得到结果$$$3$$$,这意味着对角线上有一个地雷,并且其上方没有地雷。
在下图中,每个单元格都包含一个数字,表示到蓝色单元格的距离。绿色单元格是包含最近地雷的候选单元格。
然后我们询问该对角线上的三个单元格,在最后一次查询时,我们得到结果 $$$0$$$,这意味着在 $$$(2, 3)$$$ 位置发现了一个地雷。
第二个地雷位于$$$(3, 2)$$$位置。
在第二个测试用例中,我们首先询问右下角$$$(5, 5)$$$,得到结果$$$1$$$,这意味着两个邻居之一包含地雷,我们称其为地雷$$$1$$$。
然后我们询问单元格$$$(2, 2)$$$。我们可以看到这些绿色单元格与第一个查询中的绿色单元格不相交,因此它们包含另一个我的单元格,我们称其为我的$$$2$$$。
查询 $$$3$$$ 是单元格 $$$(3, 3)$$$。这些单元格包含我的$$$1$$$,但我们仍然不知道具体在哪里。尽管如此,我们可以确定我的 $$$2$$$ 唯一可能的单元格是 $$$(1, 1)$$$,因为对于此查询,所有其他候选单元的距离都比 $$$3$$$ 更近。