这是一个运行两次(通信)交互问题。
有两名玩家:玩家 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 17 211 63 52 43 41 26 79 591 21 43 43 53 85 66 78 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$$$ 中的一条边。
- 程序 是您的姓名 编译 程序。
- 参数 是您的程序需要的参数。
顶行注释包含有关工具本身的详细信息。
请注意:
- 该工具与问题的交互器并不完全相同。法官的判决可能会有所不同。
- 该工具将检查您的输入文件是否遵循格式,但它会 不 检查您的输入是否满足约束。
- 该工具将 不 检查您的程序是否符合时间/内存限制。