CF1934C Find a Mine

这是一个交互题。 你有一个 $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() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 Hack 格式： Hack 时请使用如下格式： 第一行一个整数 $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, 1)$，得到结果 $3$，这意味着有一个地雷在反对角线上，并且它上方没有地雷。 下图中，每个格子中的数字表示到蓝色格子的距离。绿色格子是可能包含最近地雷的候选格子。  然后我们在该对角线上再询问三个格子，最后一次询问得到结果 $0$，说明在 $(2, 3)$ 处找到了一个地雷。 第二个地雷位于 $(3, 2)$。 在第二个测试用例中，我们首先询问右下角 $(5, 5)$，得到结果 $1$，说明它的相邻格子中有一个地雷，记为地雷 $1$。  然后我们询问格子 $(2, 2)$。可以看到这些绿色格子与第一次询问的绿色格子没有交集，所以它们包含另一个地雷，记为地雷 $2$。  第三次询问 $(3, 3)$。这些格子包含地雷 $1$，但我们还不能确定具体位置。不过我们可以确定，唯一可能包含地雷 $2$ 的格子是 $(1, 1)$，因为其它候选格子在本次询问下距离都小于 $3$。  由 ChatGPT 4.1 翻译