AT_ahc064_a [AHC064A] Non-Crossing Railcar Rearrangement

AtCoder国の高橋鉄道から、あなたに緊急の依頼が届いた。翌朝の一斉出発に向けて、貨物ターミナルでの車両の並べ替えを手伝ってほしいというのだ。 貨物ターミナルには、列車が出発するための線路（出発線）が複数並んでおり、車両が配置されている。 また、各出発線の末尾側には、車両を一時的に移しておくための線路（待避線）が同数設けられている。 出発線と待避線の間で車両を適切に移動させることで、各出発線に車両を所定の順序で並べたい。  ただし、複数の移動を同時に行う際、出発線と待避線を結ぶ経路どうしが交差すると、車両同士が互いの進路を塞いでしまう。そのため、同じタイミングに行う移動は、経路が互いに交差しないように選ぶ必要がある。 高橋鉄道のために、できるだけ少ない手順で、全ての車両を所定の順序に並べてほしい。

貨物ターミナルには $ R $ 本の出発線が並んでおり、出発線の出口とは反対側に $ R $ 本の待避線が配置されている。 出発線および待避線には、それぞれ左から右へ順に $ 0,1,\ldots,R-1 $ の番号が付けられている。 以降、出発線については出口側を「先頭」、その反対側を「末尾」と呼ぶ。待避線については、出発線に近い側を「先頭」、その反対側を「末尾」と呼ぶ。 任意の出発線と任意の待避線の間は線路でつながっており、車両は出発線と待避線の間を移動できる。 出発線は各線 15 両、待避線は各線 20 両の容量を持ち、この容量を超えるような移動は禁止されている。 初期状態では、各出発線に 10 両ずつ車両が配置されている。 各車両には $ 0,\ldots,10R-1 $ の ID が 1 つずつ振られており、出発線 $ r $ の先頭から $ c $ 両目に配置されている車両の ID は $ Y_{r,c} $ である。待避線はすべて空である。 出発線と待避線の間で車両を移動させることによって、各出発線 $ r $ について、ID $ 10r, 10r+1, \ldots, 10r+9 $ の車両を先頭から順に並べることが目標である。 各ターンでは、以下の 2 種類の移動を**複数同時に**行うことができる。各移動は連続した $ k $ 両（ $ k \ge 1 $ ）を対象とし、その順序は保存される。 - （type = 0）出発線 $ i $ の末尾から連続する $ k $ 両を取り出し、待避線 $ j $ の先頭に連結する。 - （type = 1）待避線 $ j $ の先頭から連続する $ k $ 両を取り出し、出発線 $ i $ の末尾に連結する。  ただし、列車運行を安全に行うために、同一ターン内に行う移動は、移動方向を問わず、経路が互いに交差しないように選ばなければならない。すなわち、以下の 2 条件を満たさなければならない。 - 1 本の出発線または待避線を、同じターン内で 2 回以上使用してはならない。 - 出発線 $ i_1 $ と待避線 $ j_1 $ の間での移動、出発線 $ i_2 $ と待避線 $ j_2 $ の間での移動を同時に行う場合、 $ i_1 < i_2 $ ならば $ j_1 < j_2 $ でなければならない。 移動は最大 4000 ターン行うことができる。

入力は以下の形式で標準入力から与えられる。 > $ R $ $ Y_{0,0} $ $ \cdots $ $ Y_{0,9} $ $ \vdots $ $ Y_{R-1,0} $ $ \cdots $ $ Y_{R-1,9} $ - すべてのテストケースで、 $ R = 10 $ である。 - $ Y_{r,c} $ は、初期状態において出発線 $ r $ の先頭から $ c $ 両目（ $ 0 \leq c < 10 $ ）に配置されている車両の ID である。 - $ Y_{r,c} $ は $ 0,\ldots,10R-1 $ をちょうど 1 回ずつ含む。

操作列を以下の形式で標準出力に出力せよ。 > $ T $ $ K_0 $ $ \mathrm{type} $ $ i $ $ j $ $ k $ $ \vdots $ $ \mathrm{type} $ $ i $ $ j $ $ k $ $ \vdots $ $ K_{T-1} $ $ \mathrm{type} $ $ i $ $ j $ $ k $ $ \vdots $ $ \mathrm{type} $ $ i $ $ j $ $ k $ ここで、 $ T $ は操作を行うターン数（ $ T \leq 4000 $ ）である。 $ T $ を出力した後、各ターン $ t = 0, 1, \cdots, T-1 $ について、以下をこの順に出力する。 - まず、そのターンで実行する移動数 $ K_t $ を 1 行で出力する（ $ 1 \leq K_t \leq R $ ）。 - 続く $ K_t $ 行に、そのターンで実行する各移動を `type i j k` の形式（ $ \mathrm{type} \in \{0,1\} $ , $ 0 \leq i,j < R $ , $ k \geq 1 $ ）で出力する。 - $ \mathrm{type} = 0 $ のとき、出発線 $ i $ の末尾から $ k $ 両を取り出し、待避線 $ j $ の先頭に連結する。 - $ \mathrm{type} = 1 $ のとき、待避線 $ j $ の先頭から $ k $ 両を取り出し、出発線 $ i $ の末尾に連結する。 [例を見る](https://img.atcoder.jp/ahc064/fLqO0Ras.html?lang=ja&seed=0&output=sample)

### 得点 出力した操作列のターン数を $ T $ とする。 すべての出発線が目標配置と完全に一致している場合、 $ 100R + 4000 - T $ のスコアが得られる。 そうでない場合、最終状態の各出発線に配置された各車両（最大 $ 10R $ 両）それぞれについて、以下の得点の総和がスコアとして得られる。 - 正しい出発線に配置されている場合：1 点 - 先頭からの位置も正しい場合：追加で 9 点 ただし、ターン数が 4000 を超えた場合、または交差の制約もしくは各線の容量の制約に違反した場合は WA となる。 合計で 150 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。 ### 入力生成方法 すべてのテストケースにおいて、 $ R = 10 $ である。 整数列 $ 0,1,\ldots,10R-1 $ を一様ランダムに並び替え、並び替えた列を順に $ Y_{0,0}, Y_{0,1}, \ldots, Y_{0,9}, Y_{1,0}, \ldots, Y_{R-1,9} $ とする。 ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/ahc064/fLqO0Ras.html?lang=ja): ローカル版より高性能でアニメーション表示が可能です。 - [ローカル版](https://img.atcoder.jp/ahc064/fLqO0Ras.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/ahc064/fLqO0Ras_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。