ABC自动翻译器
搜索
首页 归档

[AHC033] A - Container Handling with Cranes

|
版权声明：署名-非商业性使用-相同方式共享 | CC BY-NC-SA 2.5 CN

A - Container Handling with Cranes

Time Limit: 3 sec / Memory Limit: 1024 MB

题面

有一个 的网格作为一个集装箱码头。假设 是左上角方块的坐标， 是从那里向下 个方块，向右 个方块的方块的坐标。共有 个集装箱，编号从 到 ，将被送入码头。请使用 台起重机，按照指定顺序进行集装箱的调度。

地图的左边缘和右边缘上分别有收集门和发运门：

  • 收集门：左边每个方块都是一个收集门，从每个收集门逐个收集 个集装箱。提前知道将会收集哪些集装箱。从位于 处的收集门收集的第 个集装箱的编号为 。
  • 发运门：右边每个方块都是一个发运门，放置在每个发运门处的集装箱会立即被外部发运。从位于 处的发运门开始，按照顺序发运编号为 的集装箱。

每个方块，包括收集门和发运门，最多只能容纳一个集装箱。除了发运门的方块以外的方块可以作为临时存储，用于调整发运顺序，因为放置在这些方块中的集装箱不会被发运。

有两种类型的起重机：一台大型起重机和 台小型起重机。最初，大型起重机放置在方块 处，每台小型起重机放置在方块 , , , 处。

每台起重机可以执行捡起集装箱、释放集装箱以及移动到相邻方块等动作。起重机始终可以移动到没有集装箱的方块。如果不携带集装箱，起重机也可以移动到有集装箱的方块。但是，携带集装箱的起重机是否可以移动到另一个有集装箱的方块取决于起重机的类型。

大型起重机可以将集装箱抬得很高，因此即使携带集装箱，它也可以移动到有其他集装箱的方块。另一方面，小型起重机将集装箱抬得较低，因此在携带集装箱时不能移动到其他集装箱的方块。

每轮，对于每台起重机，您可以独立执行以下动作之一：

  • P：捡起当前方块的集装箱。如果起重机已经携带集装箱或当前方块没有集装箱，则操作失败。
  • Q：释放携带的集装箱并放置在当前方块上。如果起重机没有携带集装箱或当前方块已经有集装箱，则操作失败。
  • U，D，L，R：向上、向下、向左或向右方向移动到相邻方块。如果小型起重机携带集装箱，则目标方块不得有集装箱。起重机不能移动到 的网格之外。
  • .：什么也不做，停留在当前方块。
  • B：炸弹起重机。如果起重机携带集装箱，则不能使用炸弹。该起重机从网格中移除，不能再执行任何动作，除了 .。

如果执行被禁止的动作，将导致操作失败。

每台起重机无论是否携带集装箱，都不能重叠或相互通过。也就是说，多台起重机不能占据同一个方块，并且两台起重机也不能以交换位置的方式移动。

由于每台起重机的操作是同时执行的，因此可以在相同轮次中将一台起重机从方块 移动到方块 ，同时将另一台起重机从方块 移动到方块 （），或炸掉方块 上的起重机。然而，如果 ，则会导致无效移动，因为这将是一个通过运动。

每轮包括以下三个步骤：

  1. 对于仍需要收集集装箱的每个收集门，如果该方块既没有集装箱也没有携带集装箱的起重机，那么将按照顺序放置下一个集装箱。
  2. 执行每台起重机的操作。
  3. 对于每个发运门，如果该方块上有集装箱，将发运集装箱并从网格中移除。

操作可以重复执行最多 轮。您的任务是找到一个操作序列，以尽可能少的轮次按照指定顺序发运集装箱。

分数

定义 ，， 和 如下：

  • ：输出操作序列中的轮次数。
  • ：从正确的发运门发运的集装箱中的逆序对总数。具体地，对于从位于 处的发运门发运的集装箱，让 为满足 的集装箱编号 的顺序， 是满足 且 的配对 总数。
  • ：从错误的发运门发运的集装箱总数。具体地，对于每个位于 处的发运门，计算其集装箱编号 不满足 的集装箱数量，把这些计数相加得到 。
  • ：未被发运的集装箱总数。

然后，您将会得到以下绝对分数。绝对得分越低越好。

对于每个测试用例，我们计算相对分数 ，其中 YOUR 是您的绝对分数，MIN 是在该测试用例中所有参赛者中获得的最低绝对分数。分数是提交的所有相对分数之和。

最终排名将由在竞赛结束后运行的更多输入的系统测试确定。在临时/系统测试中，如果您的提交产生非法输出或超出某些测试用例的时间限制，则仅该测试用例的得分为零，并且您的提交将从该测试用例的 MIN 计算中排除。

系统测试仅对最后一个收到结果的非 CE 的提交执行。请注意，在最终提交时不要出错。

测试用例数量

  • 临时测试：50
  • 系统测试：2000。我们会在比赛结束后发布 seeds.txt (sha256=502228d18e6d0d00f92654ad85f13945fc1d2865f69df352aee061a53ebf3cfa)。

关于相对评估系统

在临时/系统测试中，排名将仅计算仅收到结果的最后一个提交。只有最后的提交被用来计算相对分数的 MIN。

在排行榜中显示的分数是相对分数，每当有新的提交到达时，所有相对分数都会重新计算。另一方面，提交页面上每个提交的分数是每个测试用例的绝对分数的总和，因此不显示相对分数。为了了解排行榜中除最新提交以外的提交的相对分数，您需要重新提交。如果您的提交产生非法输出或某些测试用例超时，则提交页面上显示的得分将为 0，但排行榜显示正确回答测试用例的相对分数之和。

关于执行时间

执行时间可能会因每次执行而有所不同。此外，由于系统测试同时执行大量执行，已观察到与临时测试相比，执行时间增加了几个百分比。因此，对于接近时间限制的提交，可能会在系统测试中导致 TLE。请在程序中测量执行时间以终止处理，或者在执行时间上有足够的余量。

输入

输入以以下格式从标准输入给出。




  • 对于所有测试用例，我们固定 。
  • 是从位于 处的收集门收集的第 个集装箱的编号，并且是满足 的整数值。所有 的值互不相同。

输出

输出以以下格式从标准输出给出。



每个 是由字符 P、Q、U、D、L、R、. 和 B 组成的字符串。第 个字符表示在第 轮时位于 处的起重机的操作。每个输出字符串的长度必须在 到 之间。字符串的长度可能不同；在这种情况下，较短的字符串会在末尾填充 . 以匹配最长字符串的长度。

显示示例

输入生成

收集顺序 是通过随机打乱数字 顺序，然后按组每组 个来生成的。

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

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

输入样例 1

5
24 10 17 15 13
14 11 2 1 5
7 9 6 21 20
8 4 19 3 16
18 23 22 0 12

输出样例 1

PRDDDDRRRQLLLUUPRRRUQ
B
PRQB
PRRRRUUQB
PRRRRQB

共0条搜索结果。