AT_ahc049_a [AHC049A] Durability-Constrained Transport

AtCoder社は、新しいオフィスへ移転することにした。 コストを抑えるため、引っ越し業者には頼らず、高橋社長自ら荷物の運び出しを行うことになった。 旧オフィス内には大量のダンボール箱が平積みされており、それらをすべて出入り口まで運び出す必要がある。 ダンボール箱は積み重ねて複数同時に運ぶことができるが、重ねすぎると重さに耐えきれず潰れてしまう可能性がある。 できるだけ少ない移動回数で、すべての箱を無事に運び出す方法を考えてほしい。

$ N \times N $ マスのオフィスがある。左上のマスの座標を $ (0, 0) $ とし、下方向に $ i $ 、右方向に $ j $ 進んだ位置の座標を $ (i, j) $ とする。マス $ (0, 0) $ にはオフィスの出入り口がある。 初期状態では、出入り口を除くすべてのマスにダンボール箱が1つずつ置かれている。各ダンボール箱には、**重さ** と **耐久力** の2つの数値が定まっている。マス $ (i, j) $ にあるダンボール箱の重さは $ w_{i,j} $ 、耐久力は $ d_{i,j} $ である。 ダンボール箱は上下に積み重ねることで、複数個を同時に運ぶことができる。高橋社長の目的は、初期位置 $ (0,0) $ から開始し、以下の操作を繰り返してすべてのダンボール箱をオフィスの外に運び出すことである。 1. 現在位置にあるダンボール箱を手に持つ。すでにダンボール箱を持っている場合は、その一番上に乗せる。現在位置にダンボール箱がない場合は、この操作は行えない。 2. 手に持っているダンボール箱の山の一番上を現在位置に置く。すでにダンボール箱が置かれているマスでは、この操作は行えない。 3. 上下左右の隣接するマスに移動する。ダンボール箱が置かれているマスにも移動できるが、オフィスの外（ $ N \times N $ の範囲外）に出ることはできない。 高橋社長は非常に力持ちで、どれだけ重いダンボール箱でも一度に持つことができる。一方で、手に持っているダンボール箱の耐久力は移動（操作3）するたびに減少する。耐久力が $ 0 $ 以下になった箱は潰れてしまい、WA と判定される。 耐久力の減少量は、その箱の上に載っているダンボール箱の総重量に等しい。すなわち、現在持っているダンボール箱の重さを下から順に $ w_1, w_2, \ldots, w_n $ としたとき、下から $ i $ 番目（ $ 1 \le i \le n $ ）の箱は $ \sum_{j=i+1}^n w_j $ だけ耐久力が減少する。 耐久力が減少するのは移動（操作3）のときのみであり、操作1や操作2では変化しない。また、操作2で箱を置いても、減少した耐久力は元に戻らない。 操作3によって出入り口のあるマス $ (0,0) $ に移動すると、手に持っているダンボール箱はすべてオフィスの外に運び出される。 操作は最大で $ 2\times N^3 $ 回まで繰り返すことができる。できるだけ移動回数が少ない方法ですべてのダンボール箱を運び出してほしい。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ w_{0,0} $ $ \cdots $ $ w_{0,N-1} $ $ \vdots $ $ w_{N-1,0} $ $ \cdots $ $ w_{N-1,N-1} $ $ d_{0,0} $ $ \cdots $ $ d_{0,N-1} $ $ \vdots $ $ d_{N-1,0} $ $ \cdots $ $ d_{N-1,N-1} $ - すべてのテストケースにおいて、 $ N = 20 $ に固定されている。 - $ w_{i,j} $ はマス $ (i, j) $ に置かれているダンボール箱の重さを表す整数である。 $ (0,0) $ のマスにはダンボール箱が置かれていないため、 $ w_{0,0} = 0 $ であり、それ以外のマスに対しては $ 1 \leq w_{i,j} \leq 10^3 $ を満たす。 - $ d_{i,j} $ はマス $ (i, j) $ に置かれているダンボール箱の耐久力を表す整数である。 $ (0,0) $ のマスでは $ d_{0,0} = 0 $ 、それ以外のマスに対しては $ 10 \leq d_{i,j} \leq 3\times 10^4 $ を満たす。

$ t $ ターン目の操作を、1文字 $ a_t $ で以下のように表す。 1. 操作1を行う場合：`1` 2. 操作2を行う場合：`2` 3. 操作3を行う場合：移動方向に応じて、上：`U`、下：`D`、左：`L`、右：`R` 操作回数を $ L $ としたとき、以下の形式で標準出力に出力せよ。 > $ a_0 $ $ \vdots $ $ a_{L-1} $ [例を見る](https://img.atcoder.jp/ahc049/LDUZCjLO.html?lang=ja&seed=0&output=sample)

### 得点 操作3（移動）を行った回数を $ T $ 、オフィス内に残っているダンボール箱の個数を $ R $ とする。 このとき、以下の得点が得られる。 - $ R>0 $ の場合、 $ N^2-R $ - $ R=0 $ の場合、 $ N^2+2\times N^3-T $ ここで、 $ T $ は操作3（移動）を行った回数であり、操作1（持ち上げ）および操作2（設置）は $ T $ に含まれない。 ただし、操作回数の制限（最大 $ 2 \times N^3 $ 回）には、すべての操作が含まれる。 合計で 150 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。 ### 入力生成方法 - $ \mathrm{rand\_double}(L,U) $ : $ L $ 以上 $ U $ 以下の実数値を一様ランダムに生成する。 #### $ w $ の生成 $ (0,0) $ を除くすべてのマス $ (i,j) $ に対し、 $ w_{i,j}=\mathrm{round}(\mathrm{rand\_double}(1,\sqrt{1000})^2) $ により生成する。 #### $ d $ の生成 $ (0,0) $ を除くすべてのマス $ (i,j) $ に対し、 $ d_{i,j}=\mathrm{round}(w_{i,j}\times \mathrm{rand\_double}(10,30)) $ により生成する。 ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/ahc049/LDUZCjLO.html?lang=ja): ローカル版より高性能でアニメーション表示と手動プレイが可能です。 - [ローカル版](https://img.atcoder.jp/ahc049/LDUZCjLO.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/ahc049/LDUZCjLO_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。