← 返回题目列表

Codeforces · 1991/I

I. 网格游戏

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

这是一个交互问题。

您将获得一个包含 $$$n$$$ 行和 $$$m$$$ 列的网格。您需要用从 $$$1$$$ 到 $$$n \cdot m$$$ 的唯一整数填充每个单元格。

填满网格后,您将在该网格上与交互者玩游戏。玩家轮流从网格中选择之前未选择的单元格之一,交互器首先进行。

在第一回合,交互者可以从网格中选择任何单元格。此后,任何选定的小区必须与至少一个先前选定的小区正交相邻。如果两个单元共享一条边,则认为它们正交相邻。游戏继续进行,直到所有单元格都被选中。

您的目标是让您选择的单元格中的数字总和严格小于交互器选择的单元格中的数字总和。

输入

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

每个测试用例的唯一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$4 \le n, m \le 10$$$) - 网格中的行数和列数。

互动

首先,输出$$$n$$$行,每行包含$$$m$$$个整数,代表你在网格中填写的整数。从 $$$1$$$ 到 $$$n \cdot m$$$ 的每个整数都应该只出现一次。

然后,游戏开始。交互器和您轮流输出坐标以选择单元格,轮流 $$$n \times m$$$ 轮,交互器首先启动。

在每个玩家(无论是你还是交互者)的回合中,玩家将输出两个整数 $$$i$$$ 和 $$$j$$$ ($$$1 \le i \le n$$$, $$$1 \le j \le m$$$),表示玩家已经选择了第 $$$i$$$ 行和第 $$$j$$$ 列的单元格。该单元格不应在上一轮中被选择。另外,如果不是第一轮,则该小区必须与至少一个先前选择的小区正交相邻。

如果您的任何输出无效,陪审团将输出“-1”,您将收到错误答案判决。

在所有 $$$n \cdot m$$$ 回合结束时,如果您选择的单元格中的数字总和不严格小于交互者选择的单元格中的数字总和,陪审团将输出“-1”,您将收到错误答案的判决。

如果您的程序收到错误答案判决,则必须立即终止。否则,您可能会收到任意判决,因为您的解决方案可能正在从封闭的流中读取。

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

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

在这个问题中,黑客被禁用。

示例

输入 #1

1
4 4




3 4

4 4

4 2

4 1

1 4

1 2

2 2

2 1

输出 #1

2 3 4 10
12 6 11 15
5 13 16 8
9 7 1 14

2 4

4 3

3 3

3 1

1 3

1 1

2 3

3 2

注意

请注意,这是一个示例游戏,并不一定代表双方玩家的最佳策略。

首先,我们通过以下方式用从 $$$1$$$ 到 $$$16$$$ 的唯一整数填充 $$$4 \times 4$$$ 网格:

$$$2$$$$$$3$$$$$$4$$$$$$10$$$$$$12$$$$$$6$$$$$$11$$$$$$15$$$$$$5$$$$$$13$$$$$$16$$$$$$8$$$$$$9$$$$$$7$$$$$$1$$$$$$14$$$

接下来,游戏开始。

1. 交互者首先选择$$$(3, 4)$$$,即数字$$$8$$$。对于此选择,交互者可以选择任何数字。从下一次选择开始,每个选择的数字必须与任何先前选择的数字相邻。
2. 我们选择 $$$(2, 4)$$$,即数字 $$$15$$$,与 $$$(3, 4)$$$ 相邻。
3. 交互者选择 $$$(4, 4)$$$,即与 $$$(3, 4)$$$ 相邻的数字 $$$14$$$。
4. 我们选择 $$$(4, 3)$$$,它是与 $$$(4, 4)$$$ 相邻的数字 $$$1$$$。
5.$$$\ldots$$$
6. 继续此操作,直到选择了所有号码。

最终我们选择的数字是$$$[15, 1, 16, 5, 4, 2, 11, 13]$$$,交互者选择的数字是$$$[8, 14, 7, 9, 10, 3, 6, 12]$$$。我们选择的数字总和是$$$67$$$,小于交互者选择的数字总和$$$69$$$。因此,这场比赛我们赢了。