A - カードの回収

Time Limit: 3 sec / Memory Limit: 1024 MB

問題文

20\times 20 マスの盤面上に100枚のカードが置かれています。 一つのマスには高々一枚のカードが置かれています。 それぞれのカードには 0,1,\ldots,99 の数字が一つ書かれており、同じ数字のカードはちょうど一枚だけ存在します。

あなたの目的は高橋くんロボを操作してカードを全て回収し、最終的に回収したカードの山(山札と呼びます)が下から順に 0,1,\ldots,99 の順番になるようにすることです。 高橋くんロボは以下の命令からなる命令列を与えることで操作します。

  • U: 上に1マス移動する。現在位置が一番上のマスの場合は無効な操作となる。
  • D: 下に1マス移動する。現在位置が一番下のマスの場合は無効な操作となる。
  • L: 左に1マス移動する。現在位置が一番左のマスの場合は無効な操作となる。
  • R: 右に1マス移動する。現在位置が一番右のマスの場合は無効な操作となる。
  • 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
B - ビジュアライザ

Time Limit: 0 msec / Memory Limit: 0 KB

配点 :0点

A問題「カードの回収」のビジュアライザ用のページです。問題ページではないので回答不要です。

テストケース生成

乱数シードを指定し、ローカル実行用に指定した数のテストケースを生成・ダウンロードできます。
生成されるテストケースは、指定したシード値から1つずつ増やしたものです。
例：「Seed= 20201107、ケース数= 3」の時、各ケースのシード値は順に「20201107, 20201108, 20201109」となります。

  • 本機能はchrome上での動作を想定しています。他の環境で正常に動作する保証はなく、特にIEでは動作しないことを確認しています。
  • 本機能は当コンテスト上でのテストケースとの同一性を保証するものではありません。特に入力順序や乱数生成の仕様に差異があることが考えられますので、予めご了承ください。

Seed=

ケース数=

ビジュアライザ

入力ファイルと出力ファイルから、点数の計算および結果を可視化するビジュアライザを用意しました。

  • 本ビジュアライザはchrome上での動作を想定しています。他の環境で正常に動作する保証はなく、特にIEでは動作しないことを確認しています。
  • 本ビジュアライザから解答の提出はできません。 AtCoder A問題「カードの回収」上より解答を提出して下さい。
  • 本ビジュアライザ上で計算された点数は、当コンテスト上での点数を保証するものではありません。本ビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。
  • テキストファイルの改行コードはLFを想定しています。特にWindowsをご使用の方はご注意下さい。
  • ブラウザのwindow幅が足りない場合、表示しているマス目の段組みがズレてしまうためご注意下さい。
  • 問題文に則り、縦がX横がYです。マウスオーバーで各マスの座標を(x,y)で表示します。

問題文中の入出力例はこちら(zip)

入力ファイル：

出力ファイル：


turn

Score

0

山札

：空マス
：カード