A - Conveyor Design

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

ストーリー

AtCoder 社は、通信販売用のオリジナルグッズ を保管するための倉庫を新しく導入した。 倉庫には、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 を満たす。
  • ベルトコンベアに含まれるマス (i_{m,0},j_{m,0}),\ldots,(i_{m,l_m-1},j_{m,l_m-1}) はすべて相異なる。
  • 各 x=0,\ldots,l_m-2 に対して、マス (i_{m,x},j_{m,x}) と (i_{m,x+1},j_{m,x+1}) は上下左右に隣接している。
  • マス (i_{m,l_m-1},j_{m,l_m-1}) とマス (i_{m,0},j_{m,0}) も上下左右に隣接している。

また、すべてのベルトコンベアを通じて、各マスが含まれるベルトコンベアの個数は高々 2 個でなければならない。

ベルトコンベアを設置した後、最大 10^5 ターンの操作を行うことができる。 各ターンでは、ベルトコンベアの番号 m と方向 d\in\{-1,1\} を指定し、そのベルトコンベア上の箱および空きマスが一斉に 1 マス分だけ循環移動する。 すなわち、操作前にマス (i_{m,x},j_{m,x}) にあった箱または空きマスは、操作後にマス

\[ (i_{m,(x+d)\bmod l_m},j_{m,(x+d)\bmod l_m}) \]

へ移動する。

操作後、搬出口であるマス (0,N/2) に箱が存在し、その箱の番号が倉庫内に残っている箱の中で最も小さい場合、その箱は搬出口から取り除かれる。

ただし、初期状態で a_{0,N/2}=0 である場合、箱 0 は最初の操作を行う前に取り除かれる。

できるだけ少ない操作回数で、すべての箱を管理番号の小さい順に搬出してほしい。

得点

出力した操作列の長さを T、搬出できた箱の個数を B とする。 このとき、以下の得点が得られる。

  • B=N^2 の場合、10^6 + \mathrm{round}\left(10^6 \log_2 \frac{10^5}{T}\right)
  • B<N^2 の場合、\mathrm{round}\left(10^6\times \frac{B}{N^2}\right)

合計で 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) に置かれている箱の番号を表す。
  • 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}<N を満たす。
  • 各ベルトコンベアに含まれるマスはすべて相異なる。
  • 各ベルトコンベアにおいて、列中で隣り合うマス、および末尾のマスと先頭のマスは上下左右に隣接している。
  • 各マスが含まれるベルトコンベアの個数は高々 2 個でなければならない。
  • 0\leq T\leq 10^5
  • 各操作について、0\leq m_t<M を満たす。
  • 各操作について、d_t は -1 または 1 である。

例を見る

入力生成方法

N は 20 で固定である。

初期状態の箱の配置 a は、0 から N^2-1 までの整数をランダムな順に並べ替えることにより生成される。

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

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

Story

AtCoder Inc. has recently introduced a new warehouse to store its original merchandise sold online. The warehouse contains a large number of boxes holding items such as T-shirts, keychains, and acrylic stands, and each box is assigned a management number.

Since the boxes were brought in hastily, they were placed in locations completely unrelated to their numbers. For future inventory management, the boxes need to be taken out through the exit in increasing order of management number.

CEO Takahashi decided to install a circular conveyor belt in the warehouse and make the boxes circulate so that all boxes can be taken out with as few operations as possible.

Problem Statement

There is an N\times N warehouse. Let (0,0) be the coordinates of the top-left cell, and let (i,j) be the coordinates of the cell located i cells downward and j cells to the right from there. The cell (0,N/2) contains the exit of the warehouse.

There is exactly one box with each number from 0 to N^2-1 in the warehouse. In the initial state, the number of the box placed in cell (i,j) is a_{i,j}.

First, install at most N^2 loop-shaped devices in the warehouse. Hereafter, each loop-shaped device is called a conveyor belt.

The m-th conveyor belt is represented by a sequence of cells

\[ (i_{m,0},j_{m,0}), (i_{m,1},j_{m,1}), \ldots, (i_{m,l_m-1},j_{m,l_m-1}) \]

where l_m is the length of the conveyor belt.

Each conveyor belt must satisfy the following conditions.

  • l_m\geq 2.
  • For each x=0,\ldots,l_m-1, 0\leq i_{m,x},j_{m,x}<N.
  • The cells (i_{m,0},j_{m,0}),\ldots,(i_{m,l_m-1},j_{m,l_m-1}) contained in the conveyor belt are all distinct.
  • For each x=0,\ldots,l_m-2, the cells (i_{m,x},j_{m,x}) and (i_{m,x+1},j_{m,x+1}) are adjacent vertically or horizontally.
  • The cells (i_{m,l_m-1},j_{m,l_m-1}) and (i_{m,0},j_{m,0}) are also adjacent vertically or horizontally.

Also, over all conveyor belts, each cell must be contained in at most two conveyor belts.

After installing the conveyor belts, you may perform at most 10^5 turns of operations. In each turn, specify a conveyor belt number m and a direction d\in\{-1,1\}, and all boxes and empty cells on that conveyor belt simultaneously move circularly by one cell. That is, a box or an empty cell at cell (i_{m,x},j_{m,x}) before the operation moves after the operation to cell

\[ (i_{m,(x+d)\bmod l_m},j_{m,(x+d)\bmod l_m}) \]

After the operation, if there is a box in the exit cell (0,N/2) and its number is the smallest among the boxes remaining in the warehouse, that box is removed through the exit.

If a_{0,N/2}=0 in the initial state, box 0 is removed before the first operation is performed.

Move out all boxes in increasing order of management number using as few operations as possible.

Scoring

Let T be the length of the output operation sequence, and let B be the number of boxes successfully moved out. Then, you will obtain the following score.

  • If B=N^2, 10^6 + \mathrm{round}\left(10^6 \log_2 \frac{10^5}{T}\right)
  • If B<N^2, \mathrm{round}\left(10^6\times \frac{B}{N^2}\right)

There are 150 test cases, and the score of a submission is the total score for each test case. If your submission produces an illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA or TLE , and the score of the submission will be zero. The highest score obtained during the contest will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, they will be ranked in the same place regardless of the submission time.

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 is fixed to 20.
  • a_{i,j} represents the number of the box placed in cell (i,j) in the initial state.
  • a_{i,j} is an integer satisfying 0\leq a_{i,j}\leq N^2-1.
  • The array a contains each integer from 0 to N^2-1 exactly once.

Output

First, let M be the number of conveyor belts to install, and output it to Standard Output in the following format.

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}

Then, let T be the number of operations, and output the operation sequence in the following format.

T
m_0 d_0
\vdots
m_{T-1} d_{T-1}

In the t-th operation, the m_t-th conveyor belt is circularly shifted by one cell in direction d_t.

The output must satisfy the following conditions.

  • 0\leq M\leq N^2
  • The length l_m of each conveyor belt satisfies l_m\geq 2.
  • Each coordinate (i_{m,x},j_{m,x}) satisfies 0\leq i_{m,x},j_{m,x}<N.
  • The cells contained in each conveyor belt are all distinct.
  • For each conveyor belt, adjacent cells in the sequence, as well as the last cell and the first cell, are adjacent vertically or horizontally.
  • Each cell must be contained in at most two conveyor belts.
  • 0\leq T\leq 10^5
  • For each operation, 0\leq m_t<M.
  • For each operation, d_t is -1 or 1.

Show example

Input Generation

N is fixed to 20.

The initial placement a of the boxes is generated by randomly permuting the integers from 0 to N^2-1.

Tools (Input generator and visualizer)

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