← 返回题目列表

AtCoder · ahc064_a

A. 非交叉轨道车重新安排

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

故事

AtCoder王国的高桥铁道收到了紧急请求。他们需要您帮助重新安排货运站的火车车厢,以便第二天早上同时出发。

在货运站内,排列着几条发车轨道(出发轨道),上面放置着轨道车。 此外,在发车轨道的尾端还设有相同数量的临时存放轨道车的轨道(侧线轨道)。 通过在出发轨道和支线轨道之间适当地移动轨道车,目标是将轨道车按规定的顺序排列在每条出发轨道上。

同时执行多个移动时,如果连接出发轨道和支线轨道的路线相交,则轨道车会阻塞彼此的路径。因此,必须选择同时执行的移动,以使它们的路线不相交。

对于高桥铁道,请以尽可能少的步骤按照规定顺序排列所有车厢。

问题陈述

有 R 出发轨道布置在货运站,以及 R 侧线轨道放置在出发轨道出口的对面。 出发轨道和支线轨道均已编号 0,1,\ldots,R-1 从左到右。 以下,对于出发轨道,将出口侧的一端称为“前”,将相反的一端称为“后”。对于支线轨道,靠近出发轨道的一端称为“前”,相对的一端称为“后”。

每条出发轨道均通过铁轨连接到每条支线轨道,并且有轨车可以在出发轨道和支线轨道之间移动。 每条发车轨道可容纳15节车厢,每条支线轨道可容纳20节车厢。禁止任何超出这些容量的移动。

最初,每个出发轨道包含 10 辆有轨电车。 每辆轨道车都分配有一个唯一的 ID 0,\ldots,10R-1,以及放置在 c从出发轨道前方算起的第 - 个位置 r is Y_{r,c}。所有侧轨都是空的。 通过在出发轨道和支线轨道之间移动轨道车,目标是为每个出发轨道安排 r,有 ID 的轨道车 10r, 10r+1, \ldots, 10r+9 从前面开始按此顺序。

在每个回合中,你可以执行 同时进行多个动作 由以下两种类型的动作组成。每个动作都有手柄 k 连续轨道车(k \ge 1),并且它们的顺序被保留。

  • (类型 = 0) k 发车轨道后方的连续车厢 i 并将它们连接到侧轨的前面 j.
  • (类型 = 1) k 侧轨前方的连续车厢 j 并将它们固定在出发轨道的后部 i.

为了确保列车运行安全,必须选择在同一转弯中执行的移动,以便无论方向如何,它们的路线都不会相交。即,必须满足以下两个条件。

  • 出发轨道或支线轨道在同一回合中不得使用多次。
  • 如果在出发轨道之间移动 i_1 和壁线轨道 j_1,以及出发轨道之间的移动 i_2 和壁线轨道 j_2 同时执行,那么如果 i_1 < i_2,它必须保持 j_1 < j_2.

你最多可以执行 4000 回合的动作。

评分

让 T 是输出运动序列中的圈数。

如果所有出发航迹与目标配置完全匹配,则得分为 100R + 4000 - T.

否则,得分为最终状态下出发轨道上的每节车厢的以下分数之和(最多 10R 轨道车)。

  • 如果轨道车放置在正确的出发轨道上,则 1 分
  • 如果正面位置也正确则加9分

如果圈数超过4000,或者输出违反任何轨道的不相交约束或容量约束,则提交被判定为 WA.

有 150 测试用例,提交的分数是每个测试用例的总分。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE ,提交的分数将为零。 比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。 如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。


输入

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

R
Y_{0,0} \cdots Y_{0,9}
\vdots
Y_{R-1,0} \cdots Y_{R-1,9}
  • 在每个测试用例中, R = 10.
  • Y_{r,c} 是放置在 c从出发轨道前方算起的第 - 个位置 r 处于初始状态(0 \leq c < 10).
  • Y_{r,c} 包含每个 0,\ldots,10R-1 恰好一次。

输出

按以下格式将移动序列打印到标准输出:

T
K_0
\mathrm{type} i j k
\vdots
\mathrm{type} i j k
\vdots
K_{T-1}
\mathrm{type} i j k
\vdots
\mathrm{type} i j k

在这里, T 是执行移动的圈数 (T \leq 4000)。 打印后 T,每回合 t = 0, 1, \cdots, T-1,按此顺序打印以下内容。

  • 首先,打印该回合执行的移动次数, K_t,在一行上(1 \leq K_t \leq R).
  • 然后,打印该回合中执行的每个动作 K_t 行格式 type i j k (\mathrm{type} \in \{0,1\}, 0 \leq i,j < R, k \geq 1).
    • If \mathrm{type} = 0,取 k 发车轨道后方的火车 i 并将它们连接到侧轨的前面 j.
    • If \mathrm{type} = 1,取 k 轨道车从侧轨前方 j 并将它们固定在出发轨道的后部 i.

显示示例

输入生成

在每个测试用例中, R = 10.

生成整数序列的均匀随机排列 0,1,\ldots,10R-1,并分配元素以便 Y_{0,0}, Y_{0,1}, \ldots, Y_{0,9}, Y_{1,0}, \ldots, Y_{R-1,9}.

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

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