← 返回题目列表

Codeforces · 1934/C

C. 寻找地雷

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

这是一个交互问题。

您将获得一个包含 $$$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$$$ 更近。