Hide

Problem L
家の建築

Languages en ja sv

ニューヨーク中心部の奇人たちは、現代社会にはもう飽きてしまい、そこから引っ越したいと考えていました。 彼らは遠く離れた場所に長方形の土地を購入し、そこに住むことにしました。

土地は $N \times M$ の正方形で構成されており、それぞれの正方形に最大1つの家を建てることができます。 それぞれの正方形には、そこがどれだけ良いかを表す値 $a_{x,y}$ があり、 $0$ から $100$ の間の尺度で表されます。

彼らの目的は、他のみんなからできるだけ遠くに離れることです。 したがって、ある人が正方形の $(x,y)$ に家を建てることで得られる幸福は、$d$を他の人との最小距離としたとき、 $a_{x,y}\cdot d$ となります。

奇人たちは、距離をマンハッタン距離を用いて測定します。 $d$は、 全ての他の人の家 $(x_2, y_2)$ に対する $\min |x - x_2| + |y - y_2|$ として定義します。

奇人たちは、家を最適に配置するのを助けてほしいと思っています。 彼らの幸福度をできるだけ高くすることができるでしょうか。

入力

入力は、下記の$10$ 個のテストケースから構成されます。

最初の行には数値 $T$ ($0 \le T \le 10$) があり、テストケースの番号を表します。$0$はサンプル問題です。 次の行には数値 $N$, $M$, $K$ ($1 \le N, M \le 1\, 000$, $2 \le K \le N \cdot M$) があり、土地の縦横のマス数と人数を表します。 続く $N$ 行にはそれぞれ $M$ 個の整数があり、$a_{x,y}$ ($0 \le a_{x,y} \le 100$)を表します。

出力

$K$行でそれぞれの家の場所を出力します。それぞれの行には2個の数値で、家の行番号($1$から$N$)と列番号($1$から$M$)を含めます。 2つの家を同じ場所に建てることはできません。

得点

プログラムは、$10$ 個のテストケースでテストを行います。

投稿に対する得点は、それぞれのテストケースに対する得点の合計となります。 また、最終的な得点は最も高得点となった投稿の得点となります。 したがって、複数の投稿でそれぞれのテストケースに対して得た得点を加算することはできません。 単一のプログラムで全てのテストケースに対する得点を最大化する必要があります。

あなたのスコアは、審査員の解答に対して相対的に設定されます。 あなたの解答が審査員の解答よりも優れている場合、テストケースの得点は$10$点以上になることがあります。 しかし、合計得点は$100$点に制限されます。

サンプル問題の得点は $0$ 点です。

サンプルの説明

例題では、2つの家を $2 \times 3$ のグリッド上に配置します。 この例では、1つの家を左下に、もう1つの家を右上に配置しています。 すると、両家の最短距離は $2 + 1 = 3$ となります。 そして、幸福度の合計は $3 \cdot 30 + 3 \cdot 50 = 240$ となります。

テストケース

この問題が推測ゲームにならないように、$10$個のテストケースを説明します。

Test case

Bounds

Grid

$1$

$N = M = 100$, $K = 1\, 000$

全ての $a_{i,j}$ は同じ値です。

$2$

$N = M = 100$, $K = 500$

$a_{i,j}$$0$から$100$までの間でランダムに選ばれます。

$3$

$N = 200$, $M = 1$, $K = 30$

$a_{i,j}$$0$から$100$までの間でランダムに選ばれます。

$4$

$N = M = 1\, 000$, $K = 40\, 000$

$a_{i,j}$$0$から$100$までの間でランダムに選ばれます。

$5$

$N = M = 100$, $K = 20$

$a_{i,j} = \min (100, \max (0, i + r))$, $r$$-5$から$5$まででランダムに選ばれます。$i$$0$起点の行番号です。

$6$

$N = M = 1\, 000$, $K = 10\, 000$

$a_{i,j} = \min (100, \max (0, \lfloor 0.101 \cdot i \rfloor + r))$, $r$$-5$から$5$まででランダムに選ばれます。

$7$

$N = M = 100$, $K = 500$

$a_{i,j} = \lfloor 100 / r \rceil $, $r$$1$から$200$までの実数でランダムに選ばれます。

$8$

$N = M = 100$, $K = 500$

$a_{i,j} = \lfloor 100 / r^2 \rceil $, $r$$1$から$200$までの実数でランダムに選ばれます。

$9$

$N = M = 1\, 000$, $K = 40\, 000$

$a_{i,j} = \lfloor 100 / r^2 \rceil $, $r$$1$から$200$までの実数でランダムに選ばれます。

$10$

$N = M = 100$, $K = 9$

$50$マスのランダムに選ばれた$0$のマスを除き、$1$です。多くはサイズが $10 \times 10$ ですが、より大きいものもあります。

「ランダム」は、次の意味です。 連続一様分布. $\lfloor x \rfloor $$x$ の切り捨て、$\lfloor x \rceil $$x$ の切り上げを意味します。

サンプル入力 1 サンプル出力 1
0
2 3 2
50 60 50
30 50 40
2 1
1 3