AT_ahc065_a [AHC065A] Conveyor Design

AtCoder 社は、[通信販売用のオリジナルグッズ](https://suzuri.jp/AtCoder/products) を保管するための倉庫を新しく導入した。 倉庫には、T シャツやキーホルダー、アクリルスタンドなどが入った箱が大量に並べられており、それぞれの箱には管理番号が付けられている。 ところが、搬入作業を急いだため、箱は番号順とはまったく関係のない場所に置かれてしまった。 今後の在庫管理のため、箱を管理番号の小さい順に搬出口へ取り出したい。 そこで、高橋社長は、倉庫内に環状のベルトコンベアを設置し、箱をうまく循環移動させることで、できるだけ少ない操作回数ですべての箱を取り出そうと考えた。

$ N\times N $ マスの倉庫がある。 一番左上のマスの座標を $ (0,0) $ とし、そこから下方向に $ i $ マス、右方向に $ j $ マス進んだ先のマスの座標を $ (i,j) $ とする。 マス $ (0,N/2) $ には倉庫の搬出口がある。 倉庫には $ 0 $ から $ N^2-1 $ までの番号が付いた箱が、それぞれ 1 個ずつ置かれている。 初期状態でマス $ (i,j) $ に置かれている箱の番号は $ a_{i,j} $ である。 まず初めに、倉庫内にループ状の装置を最大 $ N^2 $ 個まで設置せよ。 以下では、1 つのループ状の装置を **ベルトコンベア** と呼ぶ。 $ m $ 番目のベルトコンベアは、マス列 \\\[ (i\_{m,0},j\_{m,0}), (i\_{m,1},j\_{m,1}), \\ldots, (i\_{m,l\_m-1},j\_{m,l\_m-1}) \\\] によって表される。 ここで、 $ l_m $ はベルトコンベアの長さである。 各ベルトコンベアは、以下の条件を満たす必要がある。 - $ l_m\geq 2 $ である。 - 各 $ x=0,\ldots,l_m-1 $ に対して、 $ 0\leq i_{m,x},j_{m,x}

入力は以下の形式で標準入力から与えられる。 > $ 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) $ に置かれている箱の番号を表す。 - $ a_{i,j} $ は $ 0\leq a_{i,j}\leq N^2-1 $ を満たす整数である。 - 配列 $ a $ には $ 0 $ から $ N^2-1 $ までの整数がそれぞれちょうど 1 回ずつ現れる。

まず、設置するベルトコンベアの個数を $ M $ として、以下の形式で標準出力へ出力せよ。 > $ M $ $ l_0 $ $ i_{0,0} $ $ j_{0,0} $ $ \cdots $ $ i_{0,l_0-1} $ $ j_{0,l_0-1} $ $ \vdots $ $ l_{M-1} $ $ i_{M-1,0} $ $ j_{M-1,0} $ $ \cdots $ $ i_{M-1,l_{M-1}-1} $ $ j_{M-1,l_{M-1}-1} $ 続いて、操作回数を $ T $ とし、以下の形式で操作列を出力せよ。 > $ T $ $ m_0 $ $ d_0 $ $ \vdots $ $ m_{T-1} $ $ d_{T-1} $ $ t $ 回目の操作では、 $ m_t $ 番目のベルトコンベアを方向 $ d_t $ へ 1 マス分だけ循環移動させる。 出力は以下の条件を満たさなければならない。 - $ 0\leq M\leq N^2 $ - 各ベルトコンベアの長さ $ l_m $ は $ l_m\geq 2 $ を満たす。 - 各座標 $ (i_{m,x},j_{m,x}) $ は $ 0\leq i_{m,x},j_{m,x}

### 得点 出力した操作列の長さを $ T $ 、搬出できた箱の個数を $ B $ とする。 このとき、以下の得点が得られる。 - $ B=N^2 $ の場合、 $ 10^6 + \mathrm{round}\left(10^6 \log_2 \frac{10^5}{T}\right) $ - $ B