← 返回题目列表

Codeforces · 1493/F

F. 魔法矩阵

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

这是一个交互问题。

存在一个大小为 $$$n \times m$$$ 的矩阵 $$$a$$$ ($$$n$$$ 行和 $$$m$$$ 列),你只知道数字 $$$n$$$ 和 $$$m$$$。矩阵的行从上到下编号为 $$$1$$$ 到 $$$n$$$,矩阵的列从左到右编号为 $$$1$$$ 到 $$$m$$$。第 $$$x$$$ 行和第 $$$y$$$ 列交叉处的单元格表示为 $$$(x, y)$$$。

你被要求找到对的数量 $$$(r, c)$$$ ($$$1 \le r \le n$$$, $$$1 \le c \le m$$$, $$$r$$$ 是 $$$n$$$ 的约数, $$$c$$$ 是 $$$m$$$ 的约数),这样如果我们将矩阵分割成大小为 $$$r 的矩形\times c$$$ (高度为 $$$r$$$ 行,宽度为 $$$c$$$ 列,每个单元格恰好属于一个矩形),所有这些矩形都是两两相等的。

您可以使用以下类型的查询:

- ? $$$h$$$ $$$w$$$ $$$i_1$$$ $$$j_1$$$ $$$i_2$$$ $$$j_2$$$ ($$$1 \le h \le n$$$, $$$1 \le w \le m$$$, $$$1 \le i_1, i_2 \le n$$$, $$$1 \le j_1, j_2 \le m$$$) — 检查矩阵 $$$a$$$ 的高度 $$$h$$$ 行和宽度 $$$w$$$ 列的非重叠子矩形是否相等。第一个矩形的左上角是$$$(i_1, j_1)$$$。第二个矩形的左上角是$$$(i_2, j_2)$$$。如果子矩形至少有一个共同的单元格,则子矩形重叠。如果查询中的子矩形坐标不正确(例如,它们超出了矩阵的边界)或重叠,则您的解决方案将被视为不正确。

您最多可以使用 $$$ 3 \cdot \left \lfloor{ \log_2{(n+m)} } \right \rfloor$$$ 查询。矩阵 $$$a$$$ 的所有元素在程序开始之前都是固定的,并且不依赖于您的查询。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 1000$$$) — 分别是行数和列数。

互动

要进行查询,请打印一行,格式为“? $$$h$$$ $$$w$$$ $$$i_1$$$ $$$j_1$$$ $$$i_2$$$ $$$j_2$$$ ”,其中整数是不重叠矩形的高度和宽度以及左上角的坐标,您想知道它们是否相等。

每次查询后读取单个整数 $$$t$$$ ($$$t$$$ 是 $$$0$$$ 或 $$$1$$$):如果子矩形相等,则 $$$t=1$$$,否则 $$$t=0$$$。

如果您的查询格式不正确或您提出的查询超过 $$$3 \cdot \left \lfloor{ \log_2{(n+m)} } \right \rfloor$$$ 查询,您将收到错误答案判决。

打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

保证矩阵$$$a$$$是固定的,在交互过程中不会改变。

黑客格式

对于黑客攻击,请使用以下格式。

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 1000$$$) — 分别是矩阵中的行数和列数。

接下来的 $$$n$$$ 行包含 $$$m$$$ 个整数 — 矩阵 $$$a$$$ 的元素。矩阵的所有元素必须是 $$$1$$$ 和 $$$n \cdot m$$$ 之间的整数(含这两个值)。

输出

准备好后,打印一行带有感叹号 ('!') 的行,然后打印答案 — 合适的对 $$$(r, c)$$$ 的数量。之后你的程序应该终止。

示例

输入 #1

3 4
1
1
1
0

输出 #1

? 1 2 1 1 1 3
? 1 2 2 1 2 3
? 1 2 3 1 3 3
? 1 1 1 1 1 2
! 2

注意

在示例测试中,大小为 $$$3 \times 4$$$ 的矩阵 $$$a$$$ 等于: