루미 알고리즘

#1554플래티넘Mountain Allocation

PO 2023 결선코딩출제 Olle Lapidus, Alexander Wahlsten영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

The Danes are envious that all other countries have much better ski slopes. The issue has been brought all the way to the European Court of Justice, and it has been decided that the borders of European countries should be redrawn so that the distribution of ski slopes is as fair as possible. Europe can be modeled as a grid of size R × C, where the cell at row i, column j has a number m_ij indicating how many mountains are in that cell. A country consists of a contiguous collection of cells, where the total number of mountains in the country divided by the area of the country determines how pleasant it is to ski there. A country is contiguous if it is possible to move within the country from each cell to every other cell, by moving only in the four cardinal directions (i.e., not diagonally). Help the Danes to divide Europe into N countries so that the mountains are distributed as evenly as possible relative to the countries' areas!

Input

The first line contains the integer T, the number of the testcase. The second line contains three integers R, C (2 ≤ R × C ≤ 10^5), and N (1 ≤ N ≤ 16000), representing the number of rows and columns in the grid, and the number of countries, respectively. Then, there are R lines, one for each row in the grid. Each row contains C numbers. In row i, column j the number m_ij (0 ≤ m_ij ≤ 1000) represents the number of mountains at the corresponding location in the grid.

Output

The N countries are numbered from 0 to N - 1. Print R rows with C numbers each, where each number indicates the country number that owns the cell after your division.

Points

Your solution will be tested on 10 test cases, each of which can earn up to 10 points. Let a_k be the total number of mountains in country k divided by the number of cells in the country, and let ā be the total number of mountains divided by the total number of cells in the entire grid. You want to minimize the value of the expression

S = ∑_{k=1}^N(a_k - ā)^2.

If S = 0, your solution will earn 10 points for the test case. Otherwise, your score is determined by the expression

10 × max(1, (S_D)/S),

where S_D is what the judge's solution achieved on the same test case.

GroupPoint valueConstraints
110R = C = N = 10
210R = 1, C = 100000, N = 1000
310R = 2, C = 10000, N = 1000
410R = C = 200, N = 40, m_ij = 0 or m_ij = 1 for all i, j
510R = C = 50, N = 250
610R = C = 200, N = 2
710R = C = 200, N = 400
810R = C = 400, N = 16000
910R = C = 400, N = 1600
1010R = C = 400, N = 1600

Explanation of Sample 1

(그림은 원문 저장소에서 볼 수 있습니다)

Figure 1: Division of countries in Sample 1.

In the first sample, ā = (1 + 5 + 2 + 4)/4 = 3. The average values are 3 for the red country, 2 for the blue country, and 4 for the green country. This gives S = 2.

Explanation of Sample 2

(그림은 원문 저장소에서 볼 수 있습니다)

Figure 2: Division of countries in Sample 2.

In the second sample, ā = 4. The average value in each country is 4. This gives S = 0, which is a perfect solution.

예제

예제 1

입력
0
2 2 3
1 5
4 2
출력
0 0 
1 2 

예제 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 

출처 표기

출처: Programmeringsolympiaden 2023년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.