Problem G
Husbygge
Languages
en
ja
sv
Ett antal excentriker från centrala New York har bestämt sig för att de har fått nog av det moderna samhället, och vill flytta därifrån. Tillsammans har de köpt en rektangulär bit mark långt borta, och ska nu bosätta sig där.
Marken består av $N \times M$ rutor, och det går att bygga högst ett hus på en given ruta. Varje ruta har ett värde $a_{x,y}$ som beskriver hur trevlig den är, på en skala mellan $0$ och $100$.
Excentrikernas mål är att komma så långt bort som möjligt från alla andra, inklusive varandra. Lyckan en excentriker upplever av att bygga sitt hus på ruta $(x,y)$ är därmed $a_{x,y} \cdot d$, där $d$ är det minsta avstånd till någon annan person. Av vana använder sig excentrikerna av manhattanavstånd för att mäta detta; $d$ definieras alltså som $\min |x - x_2| + |y - y_2|$ över alla andra personers rutor $(x_2, y_2)$.
Excentrikerna vill nu ha din hjälp med att placera sina hus optimalt, så att summan av lyckan de upplever är så hög som möjligt. Kan du hjälpa dem?
Indata
Indatan består av $10$ testfall, som beskrivs längre ner.
Den första raden innehåller talet $T$ ($0 \le T \le 10$), som beskriver numret på testfallet ($0$ för sample). Den andra raden innehåller talen $N$, $M$ och $K$ ($1 \le N, M \le 1\, 000$, $2 \le K \le N \cdot M$) – höjden och bredden på markrutnätet, och antalet personer. De följande $N$ raderna innehåller $M$ heltal vardera – värdena $a_{x,y}$ ($0 \le a_{x,y} \le 100$).
Utdata
Skriv ut $K$ rader med husens positioner. Varje rad ska innehålla två tal: först raden för huset (mellan $1$ och $N$), därefter kolumnen (mellan $1$ och $M$). Två hus får inte placeras på samma position.
Poängsättning
Ditt program kommer att testas på $10$ testfall, och poängsättas baserat på hur det står sig relativt alla andra deltagare.
Din poäng för en inskickning är summan av poängen för testfallen, och din totala poäng är poängen för den bästa inskickningen. Det går alltså inte att kombinera testfall mellan olika inskickningar, utan du måste skicka in ett enda program som maximerar din poäng på alla testfall samtidigt.
Under själva tävlingen kommer din poäng sättas relativt en domarlösning; efter att den slutat kommer alla lösningar att rättas om mot de bästa deltagarlösningarna. Om din lösning är bättre än den domarna slängt ihop är det därmed möjligt att du tillfälligt får mer än $10$ poäng på ett testfall. Din (temporära) totalpoäng kommer dock att begränsas till $100$.
Sampletestfallet kommer alltid att ge $0$ poäng.
Förklaring av exampelfall
I exempelfallet vill vi placera ut två hus på ett $2 \times 3$ rutnät. Exempellösningen placerar ett av husen i det nedre vänstra hörnet och ett i det övre högra hörnet. Båda husens kortaste avstånd till något annat hus kommer då bli $2 + 1 = 3$, och summan av lycka därmed $3 \cdot 30 + 3 \cdot 50 = 240$.
Testfall
För att undvika att problemet blir en gissningslek kommer här beskrivningar av de $10$ testfallen som förekommer:
|
Testfall |
Gränser |
Rutnät |
|
$1$ |
$N = M = 100$, $K = 1\, 000$ |
Alla värden $a_{i,j}$ är samma. |
|
$2$ |
$N = M = 100$, $K = 500$ |
$a_{i,j}$ är slumpmässig mellan $0$ och $100$. |
|
$3$ |
$N = 200$, $M = 1$, $K = 30$ |
$a_{i,j}$ är slumpmässig mellan $0$ och $100$. |
|
$4$ |
$N = M = 1\, 000$, $K = 40\, 000$ |
$a_{i,j}$ är slumpmässig mellan $0$ och $100$. |
|
$5$ |
$N = M = 100$, $K = 20$ |
$a_{i,j} = \min (100, \max (0, i + r))$, där $r$ är slumpmässig mellan $-5$ och $5$, och $i$ är radnumret, nollindexerat. |
|
$6$ |
$N = M = 1\, 000$, $K = 10\, 000$ |
$a_{i,j} = \min (100, \max (0, \lfloor 0.101 \cdot i \rfloor + r))$, där $r$ är slumpmässig mellan $-5$ och $5$. |
|
$7$ |
$N = M = 100$, $K = 500$ |
$a_{i,j} = \lfloor 100 / r \rceil $, där $r$ är ett slumpmässigt flyttal mellan $1$ och $200$. |
|
$8$ |
$N = M = 100$, $K = 500$ |
$a_{i,j} = \lfloor 100 / r^2 \rceil $, där $r$ är ett slumpmässigt flyttal mellan $1$ och $200$. |
|
$9$ |
$N = M = 1\, 000$, $K = 40\, 000$ |
$a_{i,j} = \lfloor 100 / r^2 \rceil $, där $r$ är ett slumpmässigt flyttal mellan $1$ och $200$. |
|
$10$ |
$N = M = 100$, $K = 9$ |
Rutnätet består av enbart $1$:or med $50$ block av $0$:or slumpmässiga utplacerade (överlappande; de flesta med storlek $10 \times 10$, några större). |
Med slumpmässig menas här likformigt slumpmässig. $\lfloor x \rfloor $ betecknar $x$ avrundat nedåt, och $\lfloor x \rceil $ är $x$ avrundat till närmsta heltal.
| Sample Input 1 | Sample Output 1 |
|---|---|
0 2 3 2 50 60 50 30 50 40 |
2 1 1 3 |
