← 返回题目列表

AtCoder · ahc066_a

A. 宏控制器

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

故事

AtCoder Inc.首席执行官高桥喜欢球类运动。 然而,他在下班休息时间玩各种球,结果把球撒得到处都是。

青木副社长见状,非常生气,命令高桥立即清理他们。 无奈之下,高桥决定用自己最近购买的清洁机器人来收起球。

该机器人可以在办公室内移动,并使用前进、右转、左转和交换等基本操作捡起或放下球。 此外,附带的控制器具有宏功能,可以记录一系列操作并稍后回放。

代替高桥,使用尽可能短的操作序列将所有球放入相应的篮子中。

问题陈述

有一个 N\times N 网格。 设左上角单元格的坐标为 (0,0),并让单元格的坐标 i 细胞向下并且 j 右侧的单元格为 (i,j).

网格的外边界被墙壁包围,并且相邻单元之间也可能存在墙壁。 通过重复上、下、左、右移动,无需越墙,可以保证每个单元格都可以从其他单元格到达。

网格上有 M 球的类型和 M 篮子类型。 对于每种类型 k\ (0\leq k<M),有一个类型的球 k 和一篮子类型 k。 在初始状态下,每个单元最多包含一个球或篮子。

机器人最初位于单元 (0,0) 面向右。 它最初没有持有任何球。

您可以在机器人上执行以下四种类型的基本操作。

  • 前进 F: 向机器人当前面向的方向移动一个单元格。 如果当前单元格和目标单元格之间有墙,则机器人不会移动并保持在原地。

  • 右转 R: 顺时针旋转 90 度,但不离开当前位置。

  • 左转 L: 逆时针旋转 90 度,但不离开当前位置。

  • 交换 S: 将机器人当前持有的球与当前位置放置的球交换。 如果机器人没有拿球,而当前位置有球,则机器人会拾起该球,当前位置将变为空球。 如果机器人拿着一个球,但当前位置没有球,则会将该球放置在当前位置,并且机器人会空手。 如果机器人正在拿着一个球,并且当前位置也有一个球,则机器人将其拿着的球与当前位置的球交换。 如果机器人没有拿着球并且当前位置没有球,则不会发生任何事情。 放置在带有篮子的单元格上的球也会通过交换操作进行交换。

高桥的控制器还具有以下两种类型的操作。

  • 宏 M: 如果当前未录制宏,请开始录制宏。 如果当前正在录制宏,请停止录制并将录制的操作序列注册为新宏。

  • 播放 P: 播放最近注册的宏。 如果没有注册宏,则不会发生任何事情。

如果基本操作 F, R, L,或 S 在记录宏时执行,该操作被执行并附加到正在记录的宏的末尾。 在录制宏时执行

If P ,将回放最近注册的宏,而不是当前正在录制的宏。 此时,实际回放的基本操作序列将附加到正在录制的宏的末尾。

例如,考虑注册宏是 RFF 和操作顺序 执行 MFPM 。 首先, M 开始录制宏,然后 F 被执行并记录。 接下来, P 回放注册的宏 RFF,它也附加到正在录制的宏中。 最后, M 停止录制。 在此期间执行的基本操作的顺序是 FRFF,新注册的宏也是 FRFF.

最初,没有注册宏。 此外,最初没有录制任何宏。

上限 T 关于基本操作的数量作为输入给出。 宏展开后,至多 T 执行基本操作;的 (T+1)-st 不执行基本操作,并终止执行。 目标是使用尽可能短的操作顺序将所有球放入相应的篮子中。

评分

让 A 是输出操作序列的长度。 在这里, M 和 P 均算作一键操作。

让 V 是模拟结束时放置在相应篮子的单元格上的球的数量。

对于每个测试用例,获得以下绝对分数。

  • If V=M, A
  • If V<M, T\times (M-V)

绝对分数越低越好。

对于每个测试用例,我们计算 相对分数 \mathrm{round}(10^9\times \frac{\mathrm{MIN}}{\mathrm{YOUR}}),其中 YOUR 是您的绝对分数,MIN 是在该测试用例中获得的所有竞争对手中最低的绝对分数。提交的分数是相对分数的总和。

最终排名将由比赛结束后系统进行更多投入的测试来决定。 在临时/系统测试中,如果您的提交产生非法输出或超出某些测试用例的时间限制,则只有这些测试用例的分数为零,并且您的提交将被排除在这些测试用例的 MIN 计算之外。

系统测试将仅执行 上次提交收到的结果不是 CE 。 最后提交时请注意不要出错。

测试用例数量

  • 临时测试:50
  • 系统测试:2000年。我们将发布 种子.txt (sha256=d88ec61a00aa2dfb0be89801a7320e56550cf9c71cc2e6959f79c5eb057cf9ae) 比赛结束后。

关于相关评价体系

在临时/系统测试中,排名将仅使用收到除以下结果之外的最后提交的结果来计算: CE。 在计算相对分数时,仅使用最后提交的内容来计算每个测试用例的 MIN。

排名中显示的分数是相对的,每当有新的提交到达时,所有相对分数都会重新计算。 另一方面,提交页面上显示的每个提交的分数是每个测试用例的绝对分数的总和,并且不显示相对分数。 为了了解当前排名中除最新提交之外的提交的相对分数,您需要重新提交。 如果您提交的测试用例产生非法输出或超出时间限制,则提交页面上显示的分数将为 0,但排名显示的是正确回答的测试用例的相对分数总和。

关于执行时间

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


输入

输入由标准输入按以下格式给出。

N M T
v_0
\vdots
v_{N-1}
h_0
\vdots
h_{N-2}
b_0 c_0 d_0 e_0
\vdots
b_{M-1} c_{M-1} d_{M-1} e_{M-1}

在这里, (b_k,c_k) 代表类型球的初始位置 k,和 (d_k,e_k) 代表类型篮子的位置 k.

每个值都满足以下约束。

  • 10\leq N\leq 20
  • N/2\leq M\leq 2N
  • 1\leq T\leq 2N^2 M
  • v_{i,0} \cdots v_{i,N-2} 是一个长度为 N-1 组成 0 和 1;它的 j- 第一个字符 v_{i,j} 表示是否有(1) 或不是 (0) 细胞之间的墙 (i, j) 和细胞 (i, j+1).
  • h_{i,0} \cdots h_{i,N-1} 是一个长度为 N 组成 0 和 1;它的 j- 第一个字符 h_{i,j} 表示是否有(1) 或不是 (0) 细胞之间的墙 (i, j) 和细胞 (i+1, j).
  • 保证每个单元格都可以从其他单元格到达。
  • 所有球的初始位置和篮子的位置都是不同的。

输出

让 A 是操作序列的长度,并令 a_t 是字符 (F, R, L, S, M, P) 代表 t-第次操作。按以下格式输出到标准输出。 输出操作序列的

a_0
\vdots
a_{A-1}

长度 A 最多必须是 T.

查看示例

输入生成

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

网格生成

我们将单元格角对应的点称为“顶点”。

网格大小由下式确定 N=\mathrm{rand}(10,20)。 墙的数量由下式确定 W=\mathrm{rand}(0,N-1),并从单元之间没有墙壁的状态开始,重复以下过程 W 次。

从不与任何现有墙相邻的顶点中均匀随机选择一个顶点,从该顶点选择四个方向之一,然后延伸一堵墙,直到它与另一堵墙相邻。

初始球位置和篮位置的生成

生成 M=\mathrm{round}(N/2\times 4^{\mathrm{rand\_double}(0,1)}).

随机播放 N^2 细胞均匀随机,并使用第一个 M 单元格作为球和下一个球的初始位置 M 单元格作为篮子的位置。

的一代 T

设置坐标顺序 (i_0,j_0),\cdots,(i_{2M},j_{2M}) 如下。

  • (i_0,j_0)=(0,0)
  • (i_{2k+1},j_{2k+1})=(b_k,c_k)
  • (i_{2k+2},j_{2k+2})=(d_k,e_k)

计算 X,按顺序访问这些坐标所需的最小移动次数,其中一次移动是在四个基本方向之一上移动到相邻单元格。 生成 r=\mathrm{rand\_double}(0,1),并确定上限 T 关于基本操作的数量 T=\mathrm{round}((2X+4M)^r\times (2N^2M)^{1-r}).

工具(输入生成器和可视化工具)

请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。