Problem G
家の建築
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 |
