Problem G
Berguppdelning
Danskarna är avundsjuka på att alla andra länder har så mycket bättre skidbackar. Frågan har tagits hela vägen till EU-domstolen, och det har beslutats att man ska rita om landsgränserna i Europa så att fördelningen av skidbackar blir så jämn som möjligt. Europa kan modelleras som ett rutnät av storlek $R \times C$, där rutan på rad i, kolumn j har ett tal $m_{ij}$ som beskriver hur många berg det finns i rutan. Ett land består av en sammanhängande mängd rutor, där det totala antalet berg i landet dividerat med landets yta avgör hur trevligt det är att åka skidor där. Landet är sammanhängande om det är möjligt att inom landet gå från varje ruta till varje annan, genom att enbart röra sig i de fyra väderstrecken (alltså ej diagonalt). Hjälp danskarna att dela upp Europas $N$ länder så att bergen är fördelade så jämnt som möjligt, relativt till ländernas yta!
Indata
Den första raden innehåller ett heltal $T$, numret på det testfall som körs. Den andra raden innehåller tre heltal $R, C$ ($2 \le R \times C \le 10^5$), $N$ ($1 \le N \le 16000$), antalet rader respektive kolumner i rutnätet, och antalet länder. Därefter följer $R$ rader, en för varje rad i rutnätet. Varje rad innehåller $C$ tal. På rad $i$, kolumn $j$ står talet $m_{ij}$ ($0 \leq m_{ij} \leq 1000$), antalet berg på motsvarande plats i rutnätet.
Utdata
De $N$ länderna är numrerade från $0$ till $N - 1$. Skriv ut $R$ rader med $C$ tal vardera, där varje tal innehåller numret på landet som äger rutan efter din uppdelning.
Poängsättning
Din lösning kommer att testas på 10 testfall, där varje fall ger upp till 10 poäng. Låt $a_ k$ vara mängden berg i land $k$ dividerat med antalet rutor i landet, och låt $\bar{a}$ vara det totala antalet berg dividerat med det totala antalet rutor i hela rutnätet. Du vill minimera värdet av uttrycket
\[ S = \sum _{k=1}^{N}{(a_ k - \bar{a})^2}. \]Om $S = 0$ får din lösning 10 poäng i testfallet. Annars bestäms din poäng enligt uttrycket
\[ 10 \times \max (1, \frac{S_ D}{S}), \]där $S_ D$ är vad domarlösningen uppnådde på samma testfall.
|
Testfall |
Poäng |
Gränser |
|
$1$ |
$10$ |
$R = C = N = 10$ |
|
$2$ |
$10$ |
$R = 1$, $C = 100000$, $N = 1000$ |
|
$3$ |
$10$ |
$R = 2$, $C = 10000$, $N = 1000$ |
|
$4$ |
$10$ |
$R = C = 200$, $N = 40$, $m_{ij} = 0$ eller $m_{ij} = 1$ för alla $i$, $j$ |
|
$5$ |
$10$ |
$R = C = 50$, $N = 250$ |
|
$6$ |
$10$ |
$R = C = 200$, $N = 2$ |
|
$7$ |
$10$ |
$R = C = 200$, $N = 400$ |
|
$8$ |
$10$ |
$R = C = 400$, $N = 16000$ |
|
$9$ |
$10$ |
$R = C = 400$, $N = 1600$ |
|
$10$ |
$10$ |
$R = C = 400$, $N = 1600$ |
Förklaring av exempelfall 1
![\includegraphics[width=2cm]{sample1.png}](/problems/pofinal23.berguppdelning/file/statement/sv/img-0001.png)
I det första exempelfallet är $\bar{a} = \frac{1 + 5 + 2 + 4}{4} = 3$. Medelvärderna är 3 för det röda landet, 2 för det blåa och 4 för det gröna. Detta ger $S = 2$.
Förklaring av exempelfall 2
![\includegraphics[width=5cm]{sample2.png}](/problems/pofinal23.berguppdelning/file/statement/sv/img-0002.png)
I det andra exempelfallet är $\bar{a} = 4$. Medelvärdet i varje land är 4. Detta ger $S = 0$, alltså en perfekt lösning.
| Sample Input 1 | Sample Output 1 |
|---|---|
0 2 2 3 1 5 4 2 |
0 0 1 2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
0 4 6 6 1 2 2 3 5 3 5 6 7 4 5 3 5 7 8 7 5 3 2 2 1 2 6 2 |
0 0 0 1 1 1 0 0 0 4 1 3 0 5 5 3 3 3 5 5 5 3 2 2 |
