← 返回题目列表

Codeforces · 2163/E

E. 困境

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

这是一个运行两次(通信)问题。

有两名玩家:玩家A和玩家B。陪审团将首先与玩家A互动。玩家A结束互动后,陪审团将与玩家B互动。注意,玩家A和玩家B不能直接向对方传递信息;双方玩家只能发送信息或从陪审团接收信息,但他们可以就沟通策略达成一致。

评审团有一个 二进制网格 $$$G$$$ 的 $$$n$$$ 行和 $$$n$$$ 列(此网格的每个单元格的值为 $$$0$$$ 或 $$$1$$$)。行 $$$1$$$ 是最上面的行,列 $$$1$$$ 是最左边的列。的 连接性 如果存在一条向左、向右、向上或向下的路径,仅通过值为 $$$1$$$ 的单元格,将每对单元格 $$$(i_1,j_1)$$$ 和 $$$(i_2,j_2)$$$ 连接起来,则该网格的 被定义为 $$$1$$$ $$$G_{i_1,j_1}=G_{i_2,j_2}=1$$$。请注意,不允许沿对角线移动。保证该网格中至少存在一个值为$$$1$$$的单元格。

陪审团首先与玩家 A 互动。陪审团将给玩家 A 网格 $$$G$$$。检查完网格后,玩家 A 必须确定 两个整数 $$$r$$$ 和 $$$c$$$ 并将它们发送给评审团。在玩家 B 交互开始时,玩家 B 将收到 第 $$$r$$$ 行中的所有单元格以及第 $$$c$$$ 列中的所有单元格的值 评审团的 。请注意,玩家 B 没有获得 $$$r$$$ 和 $$$c$$$ 的值。

玩家 A 希望确保玩家 B 可以确定 $$$G$$$ 的连接性。你的任务是扮演两个玩家并找到一个策略,以便玩家 B 能够正确确定连接。请注意,此任务的通信器不是自适应的 - 也就是说,第一次运行时提供给您的网格将与用于评估连接性的网格相同。

输入

您的代码将在每次测试中运行两次。在第一次运行中,您将成为玩家 A,在第二次运行中,您将成为玩家 B。

首次运行输入

输入的第一行包含字符串 第一。这样做的目的是让您的程序认识到这是它的第一次运行,并且它应该充当玩家 A。

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

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$C$$$ ($$$2 \leq n \leq 1000, 0 \leq C \leq 1$$$) – 分别是网格的大小和连通性。

以下 $$$n$$$ 行包含有关网格的信息。这些行的第 $$$i$$$ 包含长度为 $$$n$$$ 的二进制字符串 $$$G_i$$$,表示网格的第 $$$i$$$ 行。

保证:

  • 所有测试用例的 $$$n^2$$$ 总和不超过 $$$2\cdot 10^6$$$
  • $$$C$$$ 的值与网格中的信息匹配 – 也就是说,如果 $$$C=1$$$,则网格具有 $$$1$$$ 连接性,如果 $$$C=0$$$,则网格具有 $$$0$$$ 连接性。
  • 每个网格的输入中至少有一个 $$$1$$$。

第二次运行输入

输入的第一行包含字符串 第二。这样做的目的是让您的程序认识到这是它的第二次运行,并且它应该充当玩家 B。

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。 请注意,该数字等于第一次运行输入中的 $$$t$$$。

每个测试用例的第一行恰好包含一个整数 $$$n$$$ — 第一个运行输入的第 $$$i$$$ 测试用例上给出的网格大小。

每个测试用例的第二行包含一个二进制字符串 $$$G_{r, 1}G_{r, 2}\ldots G_{r, n}$$$ - 网格第 $$$r$$$ 行的内容。请注意,整数 $$$r$$$ 是由玩家 A 在第 $$$i$$$ 个测试用例交互结束时发送给陪审团的

每个测试用例的第三行包含一个二进制字符串 $$$G_{1, c}G_{2, c}\ldots G_{n, c}$$$ - 网格的 $$$c$$$ 列中的内容。请注意,整数 $$$c$$$ 是由玩家 A 在第 $$$i$$$ 个测试用例交互结束时发送给陪审团的。

黑客

要进行 hack,请使用以下格式:

第一行应包含一个整数 $$$t$$$ $$$(1 \le t \le 10^4)$$$ — 网格数。然后,接下来应该是 $$$t$$$ 输入块。

每个输入块的第一行必须包含一个整数 $$$n$$$ $$$(2 \le n \le 1000)$$$ - 陪审团将选择的网格的大小。

接下来的 $$$n$$$ 行应包含大小为 $$$n$$$ 的二进制字符串。这些行中的第 $$$i$$$ 应包含 $$$G_{i, 1}G_{i, 2}\ldots G_{i, n}$$$ — 陪审团将选择的网格中第 $$$i$$$ 行的内容。

每个网格中必须至少存在一个值为$$$1$$$的单元格,并且所有测试用例的$$$n^2$$$总和不应超过$$$2\cdot 10^6$$$。

请注意,每个网格的连通性由陪审团决定,您不需要将其输出以进行黑客攻击。

输出

对于第一次运行,对于每个测试用例,输出两个整数 $$$r$$$ 和 $$$c$$$ ($$$1 \leq r,c \leq n$$$)。这表示您希望第二次运行接收网格的第 $$$r$$$ 行和第 $$$c$$$ 列。

对于第二次运行,对于每个测试用例,输出一个整数 $$$C$$$ ($$$0 \leq C \leq 1$$$) – 网格的连通性。

示例

输入
复制

first
2
2 1
11
10
2 0
10
01

输出
复制

2 2
2 1

输入
复制

second
2
2
10
10
2
01
10

输出
复制

1
0

注意

在第一个输入示例中,第一个网格如下:

11
10

第一次运行时,我们知道 $$$n = 2$$$。检查示例后,我们可以确定连接性为 $$$1$$$。

对于此示例,假设玩家 A 和玩家 B 已同意某种策略,其中如果连接性为 $$$1$$$,则玩家 A 应发送均以 $$$0$$$ 结尾的行和列。在本例中,行 $$$2$$$ 和列 $$$2$$$ 满足此策略。 请注意,这是一个用于演示的示例策略,使用此策略并不适用于所有情况。

然后,看看第二次运行。现在,我们是玩家 B。我们收到 $$$n = 2$$$,所选行的值为 $$$r = [1, 0]$$$,所选列的值为 $$$c = [1, 0]$$$。由于每行的最后一个数字是$$$0$$$,玩家B使用商定的策略来确定连接性是$$$1$$$。