A - Stack to Match Pairs

実行時間制限: 2 sec / メモリ制限: 1024 MiB

問題文

N\times N マスの盤面がある。 一番左上のマスの座標を (0,0) とし、そこから下方向に i マス、右方向に j マス移動した先のマスの座標を (i,j) とする。

N は偶数であり、0 から \frac{N^2}{2}-1 までの番号が書かれたカードがそれぞれ 2 枚ずつある。 初期状態では、これらのカードが各マスにちょうど1枚ずつ置かれている。

あなたは初期状態で位置 (0,0) に空の山札を持った状態から開始し、以下の操作を繰り返す。

  1. 現在位置の上下左右に隣接するマスに移動する。N\times N マスの外部に出ることはできない。
  2. 現在位置にカードがある場合、そのカードを山札の一番上に移動させることができる。これにより山札の上から2枚のカードの番号が一致した場合、それら2枚を山札から取り除く。
  3. 現在位置にカードがない場合、山札の一番上のカードを現在位置に置くことができる。山札が空である場合や、現在位置にすでにカードがある場合には、この操作は行えない。

操作は最大で 2N^3 回行うことができる。 最終的にすべてのカードを盤面および山札から取り除きたい。 移動回数 ができるだけ少ない操作手順を求めよ。 操作2および3の回数は操作回数の上限には含まれるが、評価には含まれないことに注意せよ。

得点

出力した操作列における移動回数を K、最終的に盤面および山札に残っているカードの枚数を X としたとき、以下の得点が得られる。

  • X=0 の場合、N^2+2N^3-K
  • X>0 の場合、N^2-X

合計で 150 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。

入力

入力は以下の形式で標準入力から与えられる。

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} はちょうど2つ存在する。

出力

t ターン目の操作を、1文字 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 枚のカードをランダムな順に並び替えることで生成される。

ツール(入力ジェネレータ・ビジュアライザ)

コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。

Problem Statement

There is an N\times N grid. The top-left cell has coordinates (0,0), and the cell reached by moving i cells down and j cells to the right from there has coordinates (i,j).

N is even, and for each number from 0 to \frac{N^2}{2}-1, there are exactly two cards with that number. Initially, exactly one of these cards is placed on each cell.

You start at position (0,0) with an empty deck and repeat the following operations:

  1. Move to a cell adjacent in one of the four directions (up, down, left, or right). You cannot go outside the N\times N grid.
  2. If there is a card at your current position, you may move it to the top of your deck. If the top two cards in the deck then have the same number, those two cards are removed from the deck.
  3. If there is no card at your current position, you may place the top card of your deck onto the current cell. You cannot perform this operation if your deck is empty or if there is already a card at the current cell.

You may perform up to 2N^3 operations. Your goal is to remove all cards from both the grid and your deck. Find a sequence of operations that minimizes the number of moves. Note that the number of times you perform operations 2 and 3 counts toward the operation limit, but not toward the evaluation score.

Scoring

Let K be the number of moves in your output operation sequence, and let X be the number of cards remaining on the grid and in your deck at the end. Your score is calculated as follows:

  • If X=0, then your score is N^2 + 2N^3 - K
  • If X>0, then your score is N^2 - X

Input

Input is given from Standard Input in the following format:

N
a_{0,0} \cdots a_{0,N-1}
\vdots
a_{N-1,0} \cdots a_{N-1,N-1}
  • In all test cases, N = 20 is fixed.
  • a_{i,j} represents the number written on the card initially placed at cell (i,j), and is an integer satisfying 0 \leq a_{i,j} \leq \frac{N^2}{2} - 1.
  • Each value of a_{i,j} appears exactly twice.

Output

Each operation at turn t is represented by a single character c_t as follows:

  1. For Operation 1 (move), use the direction: Up: U, Down: D, Left: L, Right: R
  2. For Operation 2 (pick up): Z
  3. For Operation 3 (place): X

Let T be the total number of operations. Output the result to Standard Output in the following format:

c_0
\vdots
c_{T-1}

Show example

Input Generation

The initial placement of cards a_{i,j} is generated by randomly shuffling all N^2 cards.

Tools (Input generator and visualizer)

Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.