← 返回题目列表

AtCoder · ahc033_a

A. 用起重机搬运集装箱

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

问题陈述

有一个集装箱码头, N \times N 网格。 让 (0,0) 是左上角正方形的坐标, (i,j) 是所在正方形的坐标 i 向下平方并 从那里向右走 j 方块。 N^2 容器,编号自 0 to N^2-1,将被带入终端。使用 N 起重机,请按指定顺序调度集装箱。

地图左右边缘分别有接收门和发送门:

  • 接收门:左边缘的每个方块都是一个接收门,从每个接收门, N 容器按顺序运入。提前知道哪些集装箱将被运进来。 j第一个集装箱从接收门运入,位于 (i,0) 有号码 A_{i,j}.
  • 调度门:右边缘的每个方格都是一个调度门,放置在每个调度门的集装箱会立即向外调度。从调度门出发 (i,N-1),容器编号 N \times i, N \times i+1, \ldots, N \times i+N-1 将按此顺序发送。

每个方格,包括接收门和发送门,最多可容纳一个集装箱。发运门以外的方格可以作为临时存放地,调整发运顺序,放置在这些方格内的集装箱不会被发运。

起重机有两种类型:一种是大型起重机,另一种是 N-1 小型起重机。最初,大型起重机被放置在广场上 (0,0),每个小起重机都放置在方格中 (1,0), (2,0), \ldots, (N-1,0).

每台起重机都可以执行诸如拾起集装箱、释放集装箱以及移动到相邻方格等动作。起重机总是可以移动到没有容器的方格。如果不携带集装箱,起重机也可以移动到有集装箱的广场。然而,承载一个集装箱的起重机是否可以移动到另一个集装箱所在的广场取决于起重机的类型。

大型起重机可以将集装箱举高,因此即使在搬运集装箱的情况下也可以与其他集装箱一起移动到广场。另一方面,小型起重机将集装箱提升到较低的高度,并且在搬运集装箱时无法与其他集装箱一起移动到广场。

每转一圈,对于每台起重机,您可以独立执行以下操作之一:

  • P:拾取当前方格的容器。如果起重机已经持有集装箱或者当前方格没有集装箱,则会导致 WA.
  • Q:释放所持有的容器并将其放置在当前方格。如果起重机没有持有集装箱或者当前方格已经有集装箱,则会导致 WA.
  • U, D, L, R:向上、下、左、右方向移动到相邻的方块。如果小型起重机正在搬运集装箱,则目的地广场不得有集装箱。起重机不能移出范围 N \times N 网格。
  • .:什么都不做并留在当前的方块中。
  • B:轰炸起重机。如果起重机拿着一个集装箱,它就不能轰炸。起重机从电网中移除,不能再执行任何动作,除了 ..

如果您执行禁止的操作,则会导致 WA.

每台起重机都不能重叠或互相通过,无论它们是否承载集装箱。换句话说,多台起重机不能占据同一个方格,两台起重机不能以交换位置的方式移动。

由于每台起重机的动作是同时执行的,因此可以将起重机从方形移动 p 到正方形 q 在将起重机从广场移出的同一回合中 q 到正方形 r (r \neq p)或轰炸广场上的起重机 q。 然而,如果 r = p,它会导致无效移动,因为这将是一个传递移动。

每回合包含以下三个步骤:

  1. 对于每个仍需引入集装箱的收货门,如果该方格既没有集装箱也没有吊运集装箱的起重机,则按顺序将下一个集装箱放置在该方格中。
  2. 执行每台起重机的操作。
  3. 对于每个调度门,如果该方格有一个集装箱,则调度该集装箱并将其从网格中移除。

操作最多可以重复 10000 转。您的任务是找到一系列操作,在短时间内尽可能按照指定的顺序分派容器。

评分

定义值 M_0, M_1, M_2,和 M_3 如下:

  • M_0:输出操作序列中的圈数。
  • M_1:从正确的调度门调度的集装箱的倒转总数。具体来说,对于从位于以下位置的发货口发货的集装箱: (i, N-1),让 B_{i,0}, \cdots, B_{i,n_i-1} 是集装箱编号的序列 b 满足 N \times i \leq b < N \times (i+1),按照派遣顺序。然后, M_1 是总对数 (i, j, k) 这样 0 \leq j < k < n_i 和 B_{i,j} > B_{i,k}.
  • M_2:从错误的调度门调度的集装箱总数。具体来说,对于每个调度门 (i, N-1),计算其编号的容器数量, b,不满足 N \times i \leq b < N \times (i+1),这些计数的总和是 M_2.
  • M_3:未发货的集装箱总数。

然后,您将获得以下绝对分数。 绝对分数越低越好。

\[ M_0+10^2M_1+10^4M_2+10^6M_3 \]

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

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

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

测试用例数量

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

关于相关评价体系

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

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

关于执行时间

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


输入

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

N
A_{0,0} \cdots A_{0,N-1}
\vdots
A_{N-1,0} \cdots A_{N-1,N-1}
  • 对于所有测试用例,我们修复 N = 5.
  • A_{i,j} 是编号 j第一个集装箱从接收门运入,位于 (i,0),它是满足以下条件的整数值 0 \leq A_{i,j} \leq N^2-1。所有值 A_{i,j} 是不同的。

输出

按以下格式输出到标准输出。

S_0
\vdots
S_{N-1}

每个 S_i 是由字符组成的字符串 P, Q, U, D, L, R, .,和 B。的 t- 第一个字符表示起重机最初位于 (i,0) 在 t第回合。每个输出字符串的长度必须介于 1 和 10000。字符串的长度可以不同;在这种情况下,较短的字符串将被填充 . 位于末尾以匹配最长字符串的长度。

显示示例

输入生成

收货订单 A_{i,j} 是通过打乱数字生成的 0, 1, \cdots, N^2-1 按随机顺序排列,然后将它们分成几组 N 每个。

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

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


示例输入 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