CF1797C Li Hua and Chess

这是一个交互题。 李明和李华正在玩一个游戏。李华有一个大小为 $n\times m$ 的棋盘。记 $(r, c)$（$1\le r\le n, 1\le c\le m$）为棋盘上第 $r$ 行（自上而下）、第 $c$ 列（自左而右）的格子。李明在棋盘上放置了一枚国王，李华需要猜出它的位置。 李华最多可以问李明 $3$ 个问题。每次提问时，他可以选择一个格子，并询问国王移动到该格子所需的最小步数。每个问题都是独立的，也就是说国王实际上并不会移动。 国王可以从 $(x, y)$ 移动到 $(x', y')$，当且仅当 $\max\{|x-x'|, |y-y'|\}=1$（如下图所示）。  国王的位置在交互开始前就已确定。 假如你是李华，请解决这个问题。

第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n, m$（$1\le n, m\le 10^9$），表示棋盘的大小，之后开始交互。 每次提问时，输出一行 "? $r$ $c$"（不含引号，$1 \leq r \leq n, 1 \leq c \leq m$）。然后你需要从标准输入读取一个整数，表示国王移动到该格子所需的最小步数。 如果你的程序提出了无效的问题或超出了提问次数，交互器会立即终止，你的程序会收到 Wrong answer 判定。 当你确定答案后，输出一行 "! $r$ $c$"（不含引号，$(r,c)$ 是国王的初始坐标）。注意，输出最终答案不计入 $3$ 次提问限制。 每次提问后不要忘记输出换行并刷新输出缓冲区，否则会收到 Idleness limit exceeded 判定。具体做法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 Hack 格式 Hack 时请使用如下格式： 第一行包含一个整数 $t$（$1 \le t \le 10^3$）。 每个测试用例的第一行包含四个整数 $n, m, r, c$（$1\le r\le n\le 10^9, 1\le c\le m\le 10^9$）。

同上。

在第 1 个测试用例中，国王在 $(2,2)$。移动到 $(2,3)$ 需要 $1$ 步，移动到 $(2,4)$ 需要 $2$ 步。  注意，示例中的提问可能并不合理，仅作为你可以提问的示例。 由 ChatGPT 4.1 翻译