← 返回题目列表

AtCoder · ahc008_a

A. 领土

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

故事

AtCoder 的首席执行官 Takahashi 热爱动物,并在 AtCoder 办公室里养了许多宠物。 AtCoder的员工不喜欢宠物打扰他们的工作,所以他们决定在办公室里放置隔断,创造一个宠物无法进入的空间。 请创造尽可能大的空间。

问题陈述

有 N 宠物和 M 人在一个地板为 30 \times 30 方块。 所有方格最初都是可通行的,并且在 30 \times 30 方格无法通行。 让 (x, y) 是行中正方形的坐标 x 从顶部(1\leq x\leq 30)和列 y 从左开始(1\leq y\leq 30)。 重复以下过程 300 转。

首先,从以下三种类型中选择每个人的动作,并同时执行每个动作。

  • 不执行任何操作并留在当前位置。
  • 选择一个与当前位置相邻的方块并使其无法通过。在本回合开始时,你不能选择包含宠物或人类的方格。 你也不能选择相邻方格包含宠物的方格。 如果你选择一个已经无法通过的方块,则不会发生任何事情。
  • 移动到相邻的可通行方块。在本回合中,不可能移动到因其他人的行动而变得无法通过的方格。

当所有人都完成该回合的动作后,每只宠物独立移动。 宠物移动的规则取决于宠物的类型,有些宠物可能会在一个回合中移动多个方块。 详细情况将在后面描述。

包含人类或宠物的方格也是可以通过的,并且每个方格可以包含任意数量的人类和宠物。

评分

结束时 300 轮,对于每个 i=1,\cdots,M,让 R_i 是从人的最终位置可到达的一组方块 i 仅通过可通行的方块,并且 n_i 是最终位置位于的宠物数量 R_i。 那么,人 i 获得满足 s_i=\frac{|R_i|}{900}\times 2^{-n_i}。 测试用例的得分是 \mathrm{round}\left(10^8\times\frac{1}{M}\sum_{i=1}^M s_i\right).

测试用例数量

  • 临时测试:100
  • 系统测试:2000年。我们将发布 种子.txt (md5=27bf0702bbe0265900374c3b6b9846b4, sha256=33973e4ded08e3a607fc2e841e14751ff110ae10154b286e7fd5f766ff86d706) 比赛后结束了。

提交的分数是每个测试用例的总分。 在临时测试中,如果您的提交产生非法输出或某些测试用例超出时间限制,则提交本身将被判定为 WA or TLE ,提交的分数将为零。 在系统测试中,如果您提交的测试用例产生非法输出或超出时间限制,则只有这些测试用例的分数为零。 注意,如果你的程序异常终止,可能会被判断为 WA 而不是 RE.

关于执行时间

每次运行的执行时间可能略有不同。 此外,由于系统测试同时执行大量执行,因此观察到与临时测试相比,执行时间增加了几个百分点。 由于这些原因,非常接近期限的提交可能会导致 TLE 在系统测试中。 请测量程序中的执行时间以终止进程,或者在执行时间上留有足够的余量。

输入和输出

首先,每个宠物的初始位置和类型以及每个人的初始位置由标准输入以以下格式给出

N
px_1 py_1 pt_1
\vdots
px_N py_N pt_N
M
hx_1 hy_1
\vdots
hx_M hy_M

N 是介于 10 和 20 代表宠物的数量。 (px_i,py_i) 表示初始位置的坐标 i第一个宠物,以及 pt_i 是介于 1 和 5 代表的类型 i- 第一个宠物。 M 是介于 5 和 10 代表人类数量。 (hx_i,hy_i) 表示初始位置的坐标 i- 第一个人类。 所有宠物和人类的初始位置保证是不同的。

读取以上信息后,重复以下过程 300 转。

首先输出一个长度的字符串 M 其中 i- 第一个字符表示 ith 人如下在标准输出的单行上。 输出后,您必须刷新标准输出。 否则,提交的内容可能会被判定为 TLE .

  • .:不执行任何操作并留在当前位置。
  • u, d, l, r:让 (x,y) 是当前位置。做正方形 (x-1,y), (x+1,y), (x,y-1),或 (x,y+1) 分别不可通行。
  • U, D, L, R:让 (x,y) 是当前位置。移动到广场 (x-1,y), (x+1,y), (x,y-1),或 (x,y+1)。

输出后, N 字符串在一行中提供给标准输入,并用空格分隔。 的 i- 第一个字符串表示移动 i该回合中的第一个宠物。 如果宠物不动,则绳子 .。 如果它确实移动,则字符串是字符序列 U, D, L,和 R 分别代表一个方块的上、下、左、右移动。

显示示例

宠物移动规则

我们定义一个基本移动如下:移动到相邻的可通行方格中随机选择的一个方格。从无法通行的方格的情况来看,这样的方格总是存在的。

每只宠物 i 执行以下动作,具体取决于 pt_i,介于 1 和 5 代表其类型。

  1. 牛:执行一个基本动作。
  2. Pig:执行两个基本动作。
  3. 兔子:执行三个基本动作。
  4. 狗:按如下方式朝目标人移动。第一个回合开始时没有目标。如果没有目标,目标人物在当前位置,或者不存在到达目标人物的路径,则从当前位置可到达的人中均匀随机选择一个人,不包括当前位置的人。如果没有这样的人,则重置为无目标并执行一个基本动作。否则,移动到与目标人距离最短的相邻可通行格子处(如果有多个这样的格子,则统一随机选择其中一个),然后执行一个基本动作。如果在第一次或第二次移动后到达目的地,则重置为无目标。
  5. 猫:按如下方式朝目标方格移动。第一个回合开始时没有目标。如果没有目标或者不存在到达目标方格的路径,则从当前位置可到达的方格中均匀随机选择一个方格,不包括当前位置。如果不存在这样的正方形,则不执行任何操作。否则,移动到相邻的一个能缩短到目标方格最短距离的可通行方格(如果有多个这样的方格,则统一随机选择其中一个),然后执行一次基本移动。如果在第一次或第二次移动后到达目的地,则重置为无目标。

输入生成

让 \mathrm{rand}(L,U) 是一个生成均匀随机整数的函数 L 和 U,包括在内。

我们通过以下方式生成宠物数量 N=\mathrm{rand}(10, 20)。 每个宠物的初始位置是从尚未选择的坐标中统一随机选择的。 我们通过以下方式生成每只宠物的类型 pt_i=\mathrm{rand}(1, 5).

我们通过以下方式生成人数 M=\mathrm{rand}(5, 10)。 每个人的初始位置是从尚未选择的坐标中统一随机选择的。

工具

  • 本地测试仪: 你需要一个编译环境 Rust 语言.
    • 对于那些不熟悉 Rust 语言环境的人,我们为 Windows 准备了预编译的二进制文件。 tools_x86_64-pc-windows-gnu.zip
    • 第一个版本包含猫移动的错误,该错误已在比赛开始后 130 分钟修复。请重新下载。
    • 我们在自述文件中添加了更多示例。如果您不知道如何使用这些工具,请参阅README。此外,如规则中所述,您可以自由分享有关如何运行所提供工具的信息。
  • 网络可视化工具:将本地测试器生成的输出粘贴到输出字段中,可以显示执行结果的动画。

比赛期间,您可以在 Twitter 上分享所提供的 Seed=0 可视化工具的输出图像(png 或 gif)。 您必须使用指定的标签和公众帐户。您只能共享seed=0 的可视化结果和分数。不要分享其他种子的分数或提及解决方案或讨论。 共享图像列表。

工具使用的输入/输出文件规范

本地测试人员的输入文件由先验信息(每只宠物的初始位置和类型,以及每个人的初始位置)组成,后跟用于生成宠物运动的随机种子值。 由于宠物的运动取决于人类的动作,因此输入文件仅包含随机种子值,而不包含特定的运动。 本地测试器将程序的输出直接写入输出文件。 您的程序可能会输出以以下内容开头的注释行 #。 可视化工具的网络版本在输出时显示注释行,这对于调试和分析可能很有用。 由于判断程序会忽略所有注释行,因此您可以提交按原样输出注释行的程序。