← 返回题目列表

Codeforces · 1887/E

E. 良好的色彩

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

Alice 建议 Bob 玩一个游戏。鲍勃不喜欢这个主意,但他无法拒绝爱丽丝,所以他要求你编写一个可以代替他玩的程序。

游戏开始时,Alice 取出一张大小为 $$$n \times n$$$ 的网格纸,其单元格最初没有着色。之后,她分别用颜色 $$$1,2,\ldots, 2n$$$ 为一些 $$$2n$$$ 单元格着色,并通知 Bob 有关这些单元格的信息。

一次,Bob 可以指向一个尚未着色的单元格,并要求 Alice 为该单元格着色。 Alice 用她选择的 $$$2n$$$ 颜色之一为该单元格着色,并通知 Bob 选择的颜色。 Bob 的移动次数不能超过 $$$10$$$,之后他需要找到一组好的四个单元格。

如果满足以下条件,一组四个单元被认为是好的:

- 集合中的所有单元格均已着色;
- 集合中没有两个单元格具有相同的颜色;
- 单元格的中心形成一个矩形,其边与网格线平行。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 200$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 1000$$$) — 网格的大小。

以下 $$$2n$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$) — 用第 $$$i$$$ 颜色着色的单元格的坐标。

保证同一测试用例的所有坐标 $$$(x_i, y_i)$$$ 成对不同。

读取每个测试用例的输入数据后,继续如下所述的交互。

互动

您的移动次数不得超过 $$$10$$$。要进行移动,请输出“? $$$x$$$ $$$y$$$” ($$$1 \leq x,y \leq n$$$)。对此,陪审团的程序将输出从 $$$1$$$ 到 $$$2n$$$ 的单个整数 - 单元格 $$$(x,y)$$$ 的颜色。

完成所有移动后(不需要进行所有 $$$10$$$ 移动,并且不需要至少进行一次移动),输出格式为 "! $$$x_1$$$ $$$x_2$$$ $$$y_1$$$ $$$y_2$$$" ($$$1 \leq x_1, x_2, y_1, y_2 \leq n, x_1 \ne x_2, y_1 \ne y_2$$$)。如果单元格 $$$(x_1, y_1)$$$、$$$(x_1, y_2)$$$、$$$(x_2, y_1)$$$、$$$(x_2, y_2)$$$ 用不同的颜色着色,陪审团的程序将输出“OK”。之后,继续下一个测试用例,如果没有剩余的测试用例,则终止程序。

否则,如果任何指定的单元格被着色为相同的颜色,或者其中一个单元格尚未着色,陪审团的程序将输出“错误”。在这种情况下,您的程序应立即终止执行以接收错误答案判决。否则,您可能会收到任意判决。

每次移动或回答后,不要忘记输出行尾并刷新输出。否则,您将得到超出空闲限制的判决。

为此,请使用:

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

请注意,交互器是自适应的,这意味着 Alice 在 Bob 移动期间用于为单元格着色的颜色不是预先固定的。

黑客

在此问题中您不能使用 hack。

示例

输入 #1

2
3
1 2
1 3
2 1
2 3
3 1
3 2

1

OK
3
1 1
1 2
1 3
2 1
2 2
2 3

OK

输出 #1

? 1 1

! 1 2 1 3








! 1 2 1 2

注意

在第一个测试用例中:

在第二个测试用例中,坐标为 $$$(1, 1), (1, 2), (2, 1), (2, 2)$$$ 的单元格最初由 Alice 用不同的颜色着色。