← 返回题目列表

Codeforces · 2215/C

C. 定向之旅

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

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

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

在交互之前,陪审团确定一棵大小为 $$$n$$$ 的无向树 $$$T$$$ 和一个整数 $$$s$$$ ($$$1\le s\le 2^{n-1}$$$)。这些价值观对于两名球员来说是一致的。

玩家 A (Neri) 首先从陪审团处收到两个整数 $$$n$$$ 和 $$$s$$$,而不获取有关树 $$$T$$$ 的额外信息。然后,陪审团将与 Neri 进行 $$$n-1$$$ 轮的互动。在每轮交互中:

  • 陪审团将向Neri揭示$$$T$$$的无向边,然后Neri需要为其分配一个方向 立即.

请注意,$$$T$$$ 的所有 $$$n-1$$$ 边在这次交互之后都是有向的,形成一个新的有向树 $$$T'$$$。

玩家 B(Mashiro)收到 Neri 和陪审团之间互动中创建的有向树 $$$T'$$$。她的任务是根据收到的信息确定 $$$s$$$ 的值。

Neri 希望确保 Mashiro 可以确定整数 $$$s$$$。你的任务是扮演两个玩家并确定两个玩家的最佳交互策略,以便 Mashiro 能够正确确定整数 $$$s$$$。

第一次运行

您的代码将在每个测试中运行两次。第一次运行时,您将成为玩家 A (Neri)。

输入

输入的第一行包含两个整数 $$$t$$$ 和 $$$q$$$ ($$$1 \le t \le 10^4$$$, $$$q=1$$$) — 测试用例的数量和运行数量。在这里,给出 $$$q=1$$$ 的目的是让你的程序认识到这是它的第一次运行,并且它应该充当玩家 A (Neri)。

对于每个测试用例,您应该首先读取两个整数 $$$n$$$ 和 $$$s$$$ ($$$3\le n \le 30$$$, $$$1\les \le 2^{n-1}$$$) — $$$T$$$ 的大小和要传递的整数。

互动

对于每个测试用例,请记住,根据上面的输入格式,您将首先收到陪审团输入的 $$$n$$$ 和 $$$s$$$。然后,您需要与陪审团互动 $$$n-1$$$ 次:

  • 首先,从陪审团中读取两个整数$$$u$$$和$$$v$$$ ($$$1\le u \lt v\le n$$$),表示$$$T$$$中有一条无向边$$$(u,v)$$$;
  • 然后,在新行上向陪审团打印两个整数 $$$a$$$ 和 $$$b$$$,并用空格分隔,其中 $$$(a,b)$$$ 是 $$$(u,v)$$$ 或 $$$(v,u)$$$。打印 $$$(a,b)=(u,v)$$$ 意味着指定方向 $$$u\rightarrow v$$$,打印 $$$(a,b)=(v,u)$$$ 意味着指定方向 $$$v\rightarrow u$$$。

请注意,您必须为当前无向边指定方向 之前 获取下一条信息。

之后,您将继续执行下一个测试用例,或者如果您已处理完每个测试用例,则程序必须终止。

交互器是 不 自适应,这意味着每个测试用例中的树 $$$T$$$ 在任何交互之前都是固定的。

每轮交互后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。

如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效交互或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。

第二次运行

在第二轮中,您是玩家 B(Mashiro)。

输入

输入的第一行包含两个整数 $$$t$$$ 和 $$$q$$$ ($$$1\le t\le 10^4$$$, $$$q=2$$$) — 测试用例的数量和运行数量。在这里,给出 $$$q=2$$$ 的目的是让你的程序认识到这是它的第二次运行,并且它应该充当玩家 B (Mashiro)。

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

接下来是 $$$n-1$$$ 行,每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1\le u,v\le n$$$),表示 $$$T'$$$ 中有一条有向边 $$$u\rightarrow v$$$。

请注意,第二次运行的测试用例可能是 已洗牌。请参阅示例测试用例以获取更多说明。

输出

对于每个测试用例,输出一个整数 $$$s$$$ — 您从 $$$T'$$$ 确定的整数。

此后,不要忘记输出行尾并刷新输出。否则,你会得到 超过空闲限制判定。然后,继续进行下一个测试用例,或者如果它是最后一个测试用例则终止程序。

黑客

此问题不允许进行黑客攻击。

$$$^{\text{*}}$$$要刷新,请使用:

  • fflush(标准输出) or cout.flush() 在 C++ 中;
  • sys.stdout.flush() 在 Python 中;
  • 请参阅其他语言的文档。

示例

输入
复制

2 1
7 21
1 6
3 5
2 4
3 4
1 2
6 7
9 59
1 2
1 4
3 4
3 5
3 8
5 6
6 7
8 9

输出
复制


6 1
3 5
4 2
3 4
1 2
7 6

1 2
1 4
3 4
3 5
8 3
5 6
6 7
9 8

输入
复制

2 2
9
8 3
9 8
1 4
3 4
1 2
5 6
6 7
3 5
7
3 4
1 2
7 6
6 1
3 5
4 2

输出
复制

59
21

注意

第一次运行:交付给 Neri 的整数 $$$s$$$ 分别为 $$$s=21$$$ 和 $$$s=59$$$。然后,根据玩家商定的一些策略,内里指挥树木。

第二次运行:请注意,测试用例在运行之间会重新排序。以下是两个测试用例的 $$$T'$$$ 插图(按第二次运行的顺序排列):

第一个测试用例的插图 第二个测试用例的插图

测试工具

为您提供了用于本地测试的命令行工具。您可以从材料中下载它。

要使用该工具,您需要安装Python。在终端中运行以下命令:

  • 在 Windows 上: python treedir_testing_tool.py [--quiet] <数据文件> <程序> <参数>
  • 在 Linux 上: python3 treedir_testing_tool.py [--quiet] <数据文件> <程序> <参数>

参数解释:

  • -q, –安静 是一个可选参数。该工具将打印其自身与您的程序之间的交互日志,启用此功能将使该工具停止打印它们。
  • 数据文件 是您提供给工具的输入文件。它应遵循以下格式:
    • 第一行包含两个整数 $$$t$$$ 和 $$$\text{seed}$$$,测试用例的数量以及用于打乱测试用例/边顺序的种子。分配 $$$\text{seed}=0$$$ 将使工具保持顺序而不打乱。
    • 对于每个测试用例,第一行包含两个整数 $$$n$$$ 和 $$$s$$$。对于接下来的 $$$n-1$$$ 行,每行包含两个整数 $$$u$$$ 和 $$$v$$$,表示 $$$T$$$ 中的一条边。
  • 程序 是您的姓名 编译 程序。
  • 参数 是您的程序需要的参数。

顶行注释包含有关工具本身的详细信息。

请注意:

  • 该工具与问题的交互器并不完全相同。法官的判决可能会有所不同。
  • 该工具将检查您的输入文件是否遵循格式,但它会 不 检查您的输入是否满足约束。
  • 该工具将 不 检查您的程序是否符合时间/内存限制。