这是一个交互问题。
给你两个正整数 $$$n$$$ 和 $$$m$$$ ($$$\bf{n \le m}$$$)。
陪审团向您隐藏了一个矩形矩阵 $$$a$$$,其中包含 $$$n$$$ 行和 $$$m$$$ 列,其中 $$$a_{i,j} \in \{ -1, 0, 1 \}$$$ 代表所有 $$$1 \le i \le n$$$ 和 $$$1 \le j \le m$$$。陪审团还选择了单元格 $$$(i_0, j_0)$$$。您的目标是找到 $$$(i_0,j_0)$$$。
在一个查询中,您给出一个单元格 $$$(i, j)$$$,然后陪审团将回复一个整数。
- 如果$$$(i, j) = (i_0, j_0)$$$,陪审团将回复$$$0$$$。
- 否则,令 $$$S$$$ 为所有 $$$x$$$ 和 $$$y$$$ 的 $$$a_{x,y}$$$ 之和,使得 $$$\min(i, i_0) \le x \le \max(i, i_0)$$$ 和 $$$\min(j, j_0) \le y \le \max(j, j_0)$$$。然后,评审团将回复 $$$|i - i_0| + |j - j_0| + |S|$$$。
通过最多进行 $$$n + 225$$$ 查询来查找 $$$(i_0, j_0)$$$。
注意:评分器不自适应:$$$a$$$ 和 $$$(i_0,j_0)$$$ 在进行任何查询之前已固定。
输入
每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 50$$$) - 测试用例的数量。测试用例的描述如下。
每个测试用例的唯一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le m \le 5000$$$) - 分别是隐藏矩阵 $$$a$$$ 的行数和列数。
保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$25 \cdot 10^6$$$。
互动
每个测试用例的交互首先读取整数 $$$n$$$ 和 $$$m$$$。
要进行查询,请输出不带引号的“? i j”($$$1 \le i \le n, 1 \le j \le m$$$)。然后,您应该读取一个整数——您的查询的答案。
如果您收到整数 $$$-1$$$ 而不是答案或有效值 $$$n$$$ 或 $$$m$$$,则意味着您的程序进行了无效查询,超出了查询限制,或者对之前的测试用例给出了错误答案。您的程序必须立即终止才能收到错误答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。
当您准备好给出最终答案时,输出不带引号的“! i j” ($$$1 \le i \le n, 1 \le j \le m$$$) — 隐藏单元格的索引。解决一个测试用例后,您的程序应该立即转移到下一个测试用例。解决所有测试用例后,您的程序应立即终止。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客
要破解,请使用以下格式:
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 50$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le m \le 5000$$$) - 隐藏矩阵的大小。
每个测试用例的第二行包含两个整数 $$$i_0$$$ 和 $$$j_0$$$ ($$$1 \le i_0 \le n, 1 \le j_0 \le m$$$) — 隐藏单元格。
然后是 $$$n$$$ 行。其中第 $$$i$$$ 包含长度为 $$$n$$$ 的字符串 $$$s_i$$$,仅包含字符 -、0 和 +。这里,如果$$$s_{ij} = \mathtt{-}$$$,则$$$a_{ij} = -1$$$;如果$$$s_{ij} = \mathtt{0}$$$,则$$$a_{ij} = 0$$$;如果$$$s_{ij} = \mathtt{+}$$$,则$$$a_{ij} = 1$$$。
所有测试用例的 $$$n \cdot m$$$ 总和不应超过 $$$25 \cdot 10^6$$$。
例如,示例输入的 hack 格式为:
$$$\texttt{2}\\ \texttt{3}\,\texttt{4} \\ \texttt{1}\,\texttt{4} \\ \texttt{+0+0} \\ \texttt{+00+} \\ \texttt{0---} \\ \texttt{1}\,\texttt{1}\\\texttt{1}\,\texttt{1}\\\texttt{0}$$$
示例
输入 #1
2 3 4 5 3 5 1 1 0
输出 #1
? 1 1 ? 3 3 ? 3 2 ! 1 4 ? 1 1 ! 1 1
注意
第一个测试用例中的隐藏矩阵: $$$1$$$$$$0$$$$$$1$$$$$$\颜色{红色}{\textbf{0}}$$$$$$1$$$$$$0$$$$$$0$$$$$$1$$$$$$0$$$$$$$0$$$$$$-1$$$$$$-1$$$$$$-1$$$
第二个测试用例中的隐藏矩阵:$$$\color{red}{\textbf{0}}$$$
请注意,示例输入和输出中的换行符是为了清楚起见,在实际交互中不会出现。