Problem G
House Building
A number of eccentrics from central New York have decided that they have had enough of modern society, and want to move from there. Together they have bought a rectangular piece of land far away, and will now settle there.
The land consists of $N \times M$ squares, and it is possible to build a maximum of one house on a given square. Each square has value $a_{x,y}$ that describes how nice it is, on a scale between $0$ and $100$.
The goal of the eccentrics is to get as far away as possible from everyone else, including each other. The happiness an eccentric experiences from building his house on square $(x,y)$ is thus $a_{x,y}\cdot d$, where $d$ is the smallest distance to another person.
Out of habit, the eccentrics use Manhattan distance to measure this; $d$ is defined as $\min |x - x_2| + |y - y_2|$ over all other people’s squares $(x_2, y_2)$.
The eccentrics now want your help in placing their houses optimally, so that the sum of the happiness they experience is as high as possible. Can you help them?
Input
The input consists of $10$ test cases, which are described below.
The first line contains the number $T$ ($0 \le T \le 10$), which describes the number of the test case ($0$ for the sample). The second line contains the numbers $N$, $M$ and $K$ ($1 \le N, M \le 1\, 000$, $2 \le K \le N \cdot M$) – the height and width of the grid, and the number of people. Then follows $N$ lines each containing $M$ integer values – the value $a_{x,y}$ ($0 \le a_{x,y} \le 100$).
Output
Print $K$ lines with the positions of the houses. Each line should contain two numbers: first the row for the house (between $1$ and $N$), then the column (between $1$ and $M$). Two houses may not be placed at the same position.
Points
Your program will be tested on $10$ test cases.
Your score for a submission is the sum of the points for the test cases, and your total points are the points for the best submission. It is therefore not possible to combine test cases between different submissions, but you must submit a single program which maximizes your score on all test cases at once.
Your score will be set relative to a judge’s solution. If your solution is better than the one the judges threw together, it is thus possible that you temporarily get more than $10$ points on a test case. However, your total points will be limited to $100$.
The sample test case will always give $0$ points.
Explanation of example case
In the example case, we want to place two houses on a $2 \times 3$ grid. The example solution places one of the houses in the lower-left corner and one in the upper-right corner. The shortest distance from both houses to another house is then $2 + 1 = 3$, and the sum of happiness thus $3 \cdot 30 + 3 \cdot 50 = 240$.
Test Cases
To avoid this problem becoming a guessing game, here are descriptions of the $10$ test cases that occur:
|
Test case |
Bounds |
Grid |
|
$1$ |
$N = M = 100$, $K = 1\, 000$ |
All $a_{i,j}$ values are the same. |
|
$2$ |
$N = M = 100$, $K = 500$ |
$a_{i,j}$ are randomly chosen between $0$ and $100$. |
|
$3$ |
$N = 200$, $M = 1$, $K = 30$ |
$a_{i,j}$ are randomly chosen between $0$ and $100$. |
|
$4$ |
$N = M = 1\, 000$, $K = 40\, 000$ |
$a_{i,j}$ are randomly chosen between $0$ and $100$. |
|
$5$ |
$N = M = 100$, $K = 20$ |
$a_{i,j} = \min (100, \max (0, i + r))$, where $r$ is a random value between $-5$ and $5$, and $i$ is the line number, $0$-indexed. |
|
$6$ |
$N = M = 1\, 000$, $K = 10\, 000$ |
$a_{i,j} = \min (100, \max (0, \lfloor 0.101 \cdot i \rfloor + r))$, where $r$ is randomly chosen between $-5$ and $5$. |
|
$7$ |
$N = M = 100$, $K = 500$ |
$a_{i,j} = \lfloor 100 / r \rceil $, where $r$ is a randomly chosen real value between $1$ and $200$. |
|
$8$ |
$N = M = 100$, $K = 500$ |
$a_{i,j} = \lfloor 100 / r^2 \rceil $, where $r$ is a randomly chosen real value between $1$ and $200$. |
|
$9$ |
$N = M = 1\, 000$, $K = 40\, 000$ |
$a_{i,j} = \lfloor 100 / r^2 \rceil $, where $r$ is a randomly chosen real value between $1$ and $200$. |
|
$10$ |
$N = M = 100$, $K = 9$ |
The grid consists of only $1$s with $50$ squares of $0$s randomly placed (overlapping; most with size $10 \times 10$, some larger). |
Here "random" means uniformly random. $\lfloor x \rfloor $ means $x$ rounded down, and $\lfloor x \rceil $ is $x$ rounded to the nearest integer.
| Sample Input 1 | Sample Output 1 |
|---|---|
0 2 3 2 50 60 50 30 50 40 |
2 1 1 3 |
