← 返回题目列表

Codeforces · 1987/H

H. 伏魔寺

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

这是一个交互问题。

给你两个正整数 $$$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}}$$$

请注意,示例输入和输出中的换行符是为了清楚起见,在实际交互中不会出现。