← 返回题目列表

AtCoder · ahc059_a

A. 堆叠以匹配对

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

问题陈述

有一个 N\times N 网格。 左上角的单元格有坐标 (0,0),并且通过移动到达的单元格 i 细胞下降并且 j 右侧的单元格有坐标 (i,j).

N 是偶数,并且对于每个数字 0 to \frac{N^2}{2}-1,恰好有两张牌具有该数字。 最初,将这些卡片中的一张准确地放置在每个单元上。

你从位置开始 (0,0) 使用空甲板并重复以下操作:

  1. 移动到四个方向(上、下、左或右)之一的相邻单元格。你不能走出 N\times N 网格。
  2. 如果你当前位置有一张卡,你可以将其移至你的牌库顶。如果这副牌中最上面的两张牌的数字相同,那么这两张牌就会从这副牌中移除。
  3. 如果你当前位置没有卡牌,你可以将你牌库最上面的卡牌放到当前格子上。如果你的牌组是空的或者当前单元格中已经有一张牌,则无法执行此操作。

您最多可以执行 2N^3 操作。 您的目标是从网格和牌组中移除所有牌。 找到最小化次数的操作序列 移动。 请注意,执行操作 2 和 3 的次数计入操作限制,但不计入评估分数。

评分

让 K 是输出操作序列中的移动次数,并让 X 是最后网格上和牌组中剩余的牌数。您的分数计算如下:

  • If X=0,那么你的分数是 N^2 + 2N^3 - K
  • If X>0,那么你的分数是 N^2 - X

输入

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

N
a_{0,0} \cdots a_{0,N-1}
\vdots
a_{N-1,0} \cdots a_{N-1,N-1}
  • 在所有测试用例中, N = 20 已修复。
  • a_{i,j} 代表最初放置在单元格的卡上写的数字 (i,j),并且是满足的整数 0 \leq a_{i,j} \leq \frac{N^2}{2} - 1.
  • 每个值 a_{i,j} 恰好出现两次。

输出

依次进行每个操作 t 由单个字符表示 c_t 如下:

  1. 对于操作 1(移动),请使用方向: 向上: U,向下: D,左: L,右: R
  2. 对于操作 2(拾取): Z
  3. 对于操作 3(地点): X

让 T 是操作总数。将结果按以下格式输出到标准输出:

c_0
\vdots
c_{T-1}

显示示例

输入生成

卡片的初始放置 a_{i,j} 是通过随机洗牌所有生成的 N^2 卡。

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

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