← 返回题目列表

AtCoder · future_contest_2021_qual_a

A. 卡片收集

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

問題文

20\times 20 方板上放置了 100 张卡片。 每个方格最多放置一张卡。 每张卡都有 写有一个数字 0,1,\ldots,99 ,并且恰好有一张具有相同数字的卡片。

你的目标是通过操作高桥君机器人来收集所有卡牌,最后从底部开始按顺序收集收集到的卡牌堆(称为牌组)。 0,1,\ldots,99 。 高桥君机器人通过发出由以下命令组成的命令序列来操作。

  • U:上移一格。如果当前位置是最上面的方块,则该操作无效。
  • D:向下移动一位。如果当前位置是底部方块,则该操作无效。
  • L:向左移动一位。如果当前位置是最左边的方块,则该操作无效。
  • R:向右移动一位。如果当前位置是最右边的方块,则该操作无效。
  • I:收集放置在当前位置的卡牌并将其放在牌堆顶部。如果当前位置的方格内没有放置任何牌,则操作无效。
  • O:将牌组顶牌放在当前位置。如果牌组中卡牌为0张或者当前位置已经放置了一张牌,则该操作无效。

高桥君机器人最初位于左上角,牌组中有 0 张牌。 执行完所有命令后,牌组将从底部开始排序。 如果显示 0,1,\ldots,99 ,则任务成功。 移动指令(U,D,L,R) 请用尽可能少的命令序列完成任务。

移动命令数 k 您将获得4000-k 分数。 卡片收集/安装顺序( 请注意,I,O) 的数量不会影响分数。 如果 k 超过4000、指令序列长度超过10000、执行无效操作或任务失败,则得分为0分。

操作示例

左上角有高桥君机器人 如果执行RRDDIUULLIRI操作,卡牌将按照0、1、2的顺序收集,移动指令总数为9。

或者, 当你执行IRIRODO操作时,你首先按照1和2的顺序收集卡片,然后按照2和1的顺序放置它们,导致如下所示的状态。

离这里更远 如果执行DIUIUI操作,卡片会按照0、1、2的顺序收集,移动指令总数为6,比之前少。 写有


入力

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

x_0 y_0
x_1 y_1
\vdots
x_{99} y_{99}

数字 i 的卡片从左上角的方块开始下降。 x_i,向右 y_i 表示它被放置在您移动到的空间中,0\leq x_i,y_i\leq 19 很满意。

出力

在一行中输出用于操作高桥君的机器人的命令序列,没有空格或换行符。

入力生成方法

卡牌放置是随机生成的。 具体来说 将 (0,0),(0,1)\ldots ,(19,19) 中长度为400的坐标字符串随机打乱, 第 i=0,1,\ldots,99 从 i 坐标处的数字 放置一张写有 i 的卡片。


入力例 1

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

出力例 1

DDDDDDDDDDDDDDDRRRRRRRRRRRRRRRRRRRIUUUUUUULLLLLLLLLLLLLLLLLLIUUUUURRRRRRRRRRRRIURRRRRRIDDDDDDDDDDDDDDDLLLLLLLLLIUUULLLLLLLIUUUUUUUUUUULIDDDDDDDDDDDDDDDDRRIUUUUUUUUUUUUULLIDDDDDDDDDDDDLIUUUUUUUUUUUUUURRRIURRRRRRIUUURRRRRIDDLLLLLLLLLLIDDDDDDDDRRIUUUULLLLIDDDDDDDDDDDDDRRRRRRRRRIUUUUUUUUUUUUUUUUUULLLLLLLLLLLLIDDDDDDDDDDDDDDDDDDRRRIUUUUUUUUUUUUUUULLIUUUURRRRRIDDDDDDDDDDRRRRRRRRRRRRIDDLLLLLLIUUUURIUULLLLLLLLLIDDDDLLIUUUURRRRRRRRRRIUUUULLLLLLLLLLLLIUURRRRRRRRRRRIDDDDDDLLIDDLLLLLLIDDDDDRRRRRRIUUUULLLLLLLLLIDDRRRRRRRRRRRRRRRRRIUULLLLLLLLLLLLLIDDDLLLIUUUUUUUUUUURRRRRRRRRRRRRRRRRIDDDDDDDDDDDDDDDDDDRIUUUUUUUUUULLLLLLLLLLIUUUUUUURRIDDDDDDRRRRRRRRIDDDDDDDDDDLLLLLLLLLLLLLLLLIUUUUUUUUUUUUUUUURRRRRRRRRRRRIDDDDDDRIDDDDDDDDLLLLLLLLLLLLLLIUUUUUUUUUUUURRRIDDDDDDDDDDLIUUUUULIDDDDDDRRRRRRRRRRIUUUUUUUUUUUULLLLLLLLLLLLLIDDDDDRRRRRRRRRRRIDDDDDDDLLLLLLLIUUUUUUUUUUUUUUURRRIDDDDDDDDDDDDRRRRRRRRRRRRIDDDDDDLLLLLLLLLLLLIUUUUUURRRRRRRRRRIUUUULLLLLLLLLLLLLLLIUULLIUUUUURRRRRRRIDDDDDDDDDDDDDDDDLLLLLLLIURRRRRRRRRRIUUUUUUUUUUUUUUULLLLIDDDDDDDDDLIUUUUUURRRRRRRRRIDDDDDDDDLLLLLLLIUUUUUURRRRILLLLLIDDDDDDDDRRRRRRRRRRRRRIDLLLLIDDRIUUUUUUUUUUUUUUUULLLLIDDDDDDLLLIUUUUULLIDDIUUULLLIDDDDLIUUUUURRRRRRRRRRRRRRIDDDDDDDDDDDDDDDDDLLLLLLLLLLLLLLIUUUUUUUUUUUURRRRRRRRRRIDDDDRRRIDDDLLLIULIDDDDRRRRRRIUUUUUUUUUUUUUUULLLLLLLLIDDDDDDDDDDDDDDDDDDDLLLLIUUUUUUULLIUURRRRIDDDDDLLLLLLLIUUUUURRRRRRRRRRRRIDDDDDDDRRIUUUUUUUUUUUUUUUULLLLLLLLLLIDDDDDDDDDDDDDDRRRRRRRRRIDDDDLLLLLLLLLIUURRIUUUUUUUUUUUUUUURRRRRRRRRRRIDDDLLLLLLLLLLLIDDDDDDDLIUUUUUUUUUIDDDDDDDDDDDDDDDDRIUUUUUUUUUUUUUUUUUURRRRRRRRRI