/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
問題文
人気ゲーム実況者として活動しているXは、撮りためた動画の整理に取り組んでいます。
動画の読み込みに時間がかかるので調べたところ、どうやらファイルの断片化が進んでいるようでした。
Xの撮りためた動画は特殊なファイルストレージに、次のような条件で保存されています。
- 1つの動画ファイルはストレージ上の縦 H 行、横 W 列に並んだセクタ上に保存されている。
- 一番左上のセクタを (0,\ 0)、一番右下のセクタを (H - 1,\ W - 1) と表す。
- ファイルは D 個のセクタに分かれて保存されており、それらのセクタの位置は (r_{0},\ c_{0}),…,\ (r_{D-1},\ c_{D-1}) である。
- 上記に現れないセクタは空いていて、何も保存されていない。
- ファイルを読み込む際には次のような制限がある。
- ファイルを読み込むにはそのファイルを構成するセクタに (r_{0},\ c_{0}),…,\ (r_{D-1},\ c_{D-1}) の順にアクセスする必要がある。
- セクタにアクセスするために位置 (a,\ b) から (c,\ d) に移動するには |c - a| + |d - b| のコストがかかる。
- ファイル読み込みコストはこの移動コストの和である。つまり
Xは swap を繰り返してファイルの断片化を解消（デフラグ）し、ファイル読み込みコストを減らすことにしました。
swap とは縦 H 行、横 W 列に並んだセクタのうち、任意の2つのセクタ（データの有無は問わない）の状態を入れ替える操作を指します。
ただし、デフラグはストレージの寿命を縮めると聞いたことがあるXは swap 操作の回数を最大 K 回までとしました。
ゲーム実況で忙しいXのかわりにデブラグを行って、ファイル読み込みコストを最小化してください。
各テストケースの得点およびこの問題の得点は、次のように計算されます。
- 1つのテストケースでは、 max(0,\ (初期状態のコスト - 最終状態のコスト)/100) の小数点以下を切り上げた整数が得点になります。
- テストケースは全部で 30 個あります。各テストケースの得点の合計が、この問題の得点になります。
入力
入力は以下の形式で標準入力から与えられます。
H W D K
r_{0} c_{0}
:
r_{D-1} c_{D-1}
- H はセクタの行数を表す整数で、H = 200 を満たします。
- W はセクタの列数を表す整数で、W = 200 を満たします。
- D はファイルデータのあるセクタ数を表す整数で、D = 16000 を満たします。
- K は swap 操作の最大回数を表す整数で、K = 4000 を満たします。
- r_{i}\ c_{i} は データの書かれているセクタの位置を表す座標で、以下の条件を満たします。
- 0 ≤ r_{i} < H
- 0 ≤ c_{i} < W
- (r_{i},\ c_{i}) はすべて異なる
出力
swap するセクタの位置の組を1行に1つ、最大 K 行まで出力してください。
セクタ (a,\ b) と (c,\ d) を入れ替える場合は、a\ b\ c\ d と出力してください。
a_{0} b_{0} c_{0} d_{0}
a_{1} b_{1} c_{1} d_{1}
:
- 同じセクタの swap も可能です。
- K行より多い出力や範囲外の swap があった場合は WA (Wrong Answer) になります。
テストケースの生成について
各ケースはテストケースジェネレータによって生成されています。
テストケースジェネレータは一様乱数にしたがってケースを生成しています。
テストケースジェネレータはページ下部のリンクより提供しています。
入力例1
5 5 5 4000 0 0 4 4 4 0 0 4 2 2
注意: この入力はテストケースとしての制約を満たしていません。
セクタの状態を以下に図示します。
ファイル読み込みコストは 8 + 4 + 8 + 4 = 24 です。
出力例1
2 2 0 4 1 2 4 4 3 1 4 0 3 3 2 2 4 3 0 4
出力された swap 実行後のセクタの状態は以下のようになります。
ファイル読み込みコストは 3 + 3 + 2 + 1 = 9 となります。
このケースでの得点は max(0, (24 - 9)/100) = 0.15 の小数点以下切り上げで 1 となります。
ジェネレータとテスター
テストケースジェネレータとテスターを次のリンクから提供しています。
ビジュアライザ
入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。
- このビジュアライザは主要なブラウザ上で動作確認を行っていますが、全ての環境で動作することを保証していません。特に、Internet Explorer 上では動作しないことが確認されています。
- このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
- このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。
ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。