← 返回题目列表

Codeforces · 1639/A

A. 寻宝

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

本次比赛中的所有问题都有相同的说法,唯一的区别是您的解决方案运行的测试。有关评分的更多信息,请参阅声明的“评分”部分。

这是一个交互问题。

想象一下,您是一位宝藏猎人,一位非常熟练的猎人。有一天,你发现了一张古老的地图,它可以帮助你致富。地图上显示了多条林业道路,每个路口都有一个宝藏。因此,你开始了你的旅程,希望找回所有隐藏的宝藏,但你还不知道有一个邪恶的巫师站在你的对面,渴望缠结这些道路并阻碍你的成就。

藏宝图表示为无向图,其中顶点对应于路口,边对应于道路。您的路径从某个固定顶点开始,并带有您已知的标签。每次你来到一个你以前没有去过的顶点,你就挖出一个宝箱,并在这个顶点放置一面旗帜。在最初的顶点,你会立即发现一个宝箱,因此,你也会立即在那里放置一面旗帜。

当您站在交界处时,您可以看到每个相邻顶点的度数以及那里是否有旗帜。从那里你看不到其他东西。此外,邪恶巫师的力量非常强大,他能够在不改变图形结构的情况下改变地图上道路和路口的位置。因此,每次您进入交叉路口 $$$v$$$ 时,从交叉路口 $$$v$$$ 出发的道路顺序可能会有所不同。但是,请记住,相邻十字路口的集合不会改变,并且您很清楚之前在每个相邻 $$$v$$$ 顶点处挖掘的宝藏。

你的目标是尽快从图表的所有顶点收集宝藏。祝狩猎顺利!

互动

在第一行,交互器打印一个整数 $$$t$$$ ($$$1 \leq t \leq 5$$$) — 您需要解决问题的地图数量。

然后,对于每个 $$$t$$$ 地图,交互器首先打印图形描述,然后在此地图上开始交互。地图描述以以下格式给出。

第一行包含四个整数 $$$n, m, start, base\_move\_count$$$ ($$$2 \leq n \leq 300$$$, $$$1 \leq m \leq min(\frac{n(n-1)}{2}, 25n)$$$, $$$1 \leq start \leq n$$$, $$$1000 \leq base\_move\_count \leq 30000$$$) — 图中的顶点和边的数量、开始旅程的顶点的标签以及一些基本移动计数,地图的分数取决于这些计数。保证陪审团有一个解决方案,以高概率使用不超过 $$$base\_move\_count$$$ 的移动来遍历地图。

接下来的 $$$m$$$ 行包含图 $$$u, v$$$ 边的描述 ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$)。保证图是连通的,不包含多条边,所有顶点的度数不超过50。

您可以在存档“map_descriptions.zip”中找到所有测试的地图描述,您可以在“竞赛材料”部分的任何存档“problem-X-materials.zip”中找到它们 - 它们都是相同的。

之后交互开始。交互器按以下格式打印顶点描述: $$$$$$R~d~deg_1~flag_1~deg_2~flag_2 \ldots deg_d~flag_d,$$$$$$ 其中 $$$d$$$ 是当前顶点的度数,$$$deg_i$$$ 是与当前顶点相邻的第 $$$i$$$ 个顶点的度数,并且$$$flag_i$$$(0 或 1)是第 $$$i$$$ 个相邻顶点是否包含标志的指示符。顶点描述中邻居的顺序由交互器每次独立地统一随机选择。请记住,您不会获得相邻顶点的实际标签。

为了响应顶点的描述,您应该打印一个整数 $$$i$$$ ($$$1 \leq i \leq d$$$),这意味着您已经选择了描述为 $$$deg_i~flag_i$$$ 的顶点。请记住在每次输出后使用刷新操作。如果您的输出无效,您将得到“错误答案”的判决。

当您至少访问过图的所有顶点一次时,交互器将打印字符串“AC”而不是顶点描述。如果您使用超过 $$$2 \cdot base\_move\_count$$$ 移动,交互器将打印字符串“F”。在这两种情况下,您必须开始阅读下一张地图的描述,或者终止程序(如果它是测试中的最后一张地图)。

下面给出了交互示例。请注意,示例中的测试与您的解决方案将要测试的测试不同。

注意

评分:
本次比赛的所有问题都有相同的说法,只是测试有所不同。每个问题包含一个测试。测试的地图描述可以在存档中查看。

每个测试都包含几张地图。

如果您对某些地图的解决方案未能获得答案“AC”或“F”,则该问题的解决方案得分将为 $$$0$$$。如果解决方案与所有 $$$t$$$ 地图上的交互器正确交互,则该任务的分数将等于每个地图的分数总和。

如果您使用 $$$moves$$$ 移动成功通过了具有 $$$n$$$ 个顶点的图形的所有顶点,则地图的分数计算如下。表示 $$$$$$base\_fraction=\frac{base\_move\_count + 1}{n},$$$$$$ $$$$$$sol\_fraction=\frac{moves+1}{n},$$$$$$$$$$$$c=\frac{90}{\sqrt{base\_fraction - 1}}。$$$$$$

然后:

- 如果 $$$ 移动 \leq base\_move\_count$$$,您将获得 $$$100-c \sqrt{sol\_fraction - 1}$$$ 点。
- 如果 $$$base\_move\_count < 移动 \leq 2 \cdot base\_move\_count$$$,您将获得 $$$20 - \frac{10\cdot(moves + 1)}{base\_move\_count + 1}$$$ 点。

对于每个问题,选择得分最高的解决方案。请注意,最大值是为整个测试选择的,而不是为每个单独的地图选择的。

参赛者的最终成绩是每道题的得分总和。