/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
パズル愛好家のXは、自ら考案した新しいパズルを解こうとしています。
Xの考案したパズルは N × N のグリッドからなっており、一番左上、右上、左下、右下のセルの座標をそれぞれ (0,\ 0),\ (0,\ N-1),\ (N-1,\ 0),\ (N-1,\ N-1) と表します。
ここで、グリッド内のあるセルの座標を (r,\ c) としたとき、下記に定義されるいずれかの領域にあると呼ぶことにします。
- \(r < N/2\) かつ \(c < N/2\) ならば、左上領域。
- \(r < N/2\) かつ \(c \geq N/2\) ならば、右上領域。
- \(r \geq N/2\) かつ \(c < N/2\) ならば、左下領域。
- \(r \geq N/2\) かつ \(c \geq N/2\) ならば、右下領域。
このパズルでは以下の操作を行うことができます。
- グリッド内のある正方形のサブグリッドを選択し、その内部を時計回りに90度回転させる。
上記操作を最大 M 回まで行って、グリッドの左上領域に赤を、右上領域に黄を、左下領域に緑を、右下領域に青を集めるのがこのパズルの目標です。
パズルを考案するのは得意でも解くのは苦手なXの代わりに、どういう操作を行えばよいか考えてあげてください。
各テストケースの得点および、この問題の得点は、次のように計算されます。
- 1つのテストケースの得点は、次のように計算されます。
- すべての操作が終了したグリッドで、
\({\it 左上領域にある赤セル数}\ +\ \)\({\it 右上領域にある黄セル数}\ +\ \)\({\it 左下領域にある緑セル数}\ +\ \)\({\it 右下領域にある青セル数}\)
を得点とする。 - すべての赤セルが左上領域に、黄セルが右上領域に、緑セルが左下領域に、青セルが右下領域に集まっている場合、これを完全解と呼び、\(M - {\it 操作回数}\) を得点に加える。
- テストケースは全部で 50 個あります。各テストケースの得点の合計が、この問題の得点になります。
入力
入力は以下の形式で標準入力から与えられます。
N M
c_{0,0} c_{0,1} \(\cdots\) c_{0,N-1}
\(\vdots\)
c_{N-1,0} c_{N-1,1} \(\cdots\) c_{N-1,N-1}
- N はグリッドの縦と横の長さを表す整数で、N=20 を満たします。
- M は操作の最大回数を表す整数で、M=1000 を満たします。
- c_{i,j} は座標 (i,\ j) のセルの初期状態を表す整数で、0=赤, 1=黄, 2=緑, 3=青 と対応します。
出力
行う操作を各行に１つずつ順番に標準出力に出力してください。
ここで、r_{i},\ c_{i} はサブグリッドの一番左上のセルの座標 (r_{i},\ c_{i}) を表し、s_{i} はサブグリッドの辺の長さを表します。
r_{0} c_{0} s_{0}
\(\vdots\)
r_{i} c_{i} s_{i}
\(\vdots\)
テストケースの生成について
各テストケースは、完全解の状態からランダムな正方形のサブグリッドを選択して反時計回りに90度回転させるのを1000回行ったものになります。
すなわち、1000回以内の操作で完全解にできることが保証されています。
入力例1
4 1000 3 2 3 2 3 3 1 0 1 1 0 1 0 0 2 2
注意: この入力はテストケースとしての制約を満たしていません。
出力例1
0 0 3 0 1 3 1 1 2 0 0 4
初期状態から最終操作後までの各グリッドのビジュアライズ結果を以下に図示しています。
完全解を達成しているので、このサンプルでの得点は、\(4 + 4 + 4 + 4 + (1000 - 4) = 1012\) になります。
ジェネレータとテスターとサンプル入力データ
テストケースジェネレータ・テスター・サンプル入力データを次のリンクから提供しています。
ヒント：サブグリッドを回転させる処理は、テスターの中に実装があります。参考にしてください。
ビジュアライザ
入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。
- このビジュアライザはデスクトップ版の Google Chrome および Mozilla Firefox の最新バージョン上で動作確認を行っています。全てのブラウザ環境で動作することを保証していません。
- このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
- このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。
ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。