투표 가치 격차 5
시간 제한1초메모리 제한512 MB
격자 지도 위 N개 주를 연결된 K개 선거구로 나누어, 선거구 인구 최댓값과 최솟값의 비율을 최소로 만드는 분할을 구한다.
문제
JOI 왕국에서 국회의원 선거가 열린다. JOI 왕국은 N개의 주로 이루어져 있다.
JOI 왕국의 지도는 H × W개의 칸으로 이루어진 직사각형 격자이다. 세로 방향으로 H개의 칸이 있고, 가로 방향으로 W개의 칸이 있다. 한 칸은 그 칸의 네 변(왼쪽, 오른쪽, 위, 아래) 중 하나를 통해 다른 칸과 연결된다. H × W개의 칸은 N개의 주로 나뉜다. 각 주는 칸들로 이루어진 연결된 영역이다. i번째 주(1 ≤ i ≤ N)에는 총 Pi명의 유권자가 있다.
당신은 JOI 중앙선거관리위원회의 위원장이다. 당신의 임무는 K명의 대표를 선출하기 위해 N개의 주를 K개의 선거구(1 ≤ K ≤ N)로 나누는 것이다. 각 선거구는 적어도 하나의 주를 포함해야 하고, 한 선거구에 속한 칸들은 연결된 영역을 이루어야 한다. 한 칸은 그 칸의 네 변(왼쪽, 오른쪽, 위, 아래) 중 하나를 통해 다른 칸과 연결된다. 꼭짓점만 공유하는 두 칸은 연결되지 않는다.
각 선거구에 대해 1/(선거구의 유권자 수)를 그 선거구의 한 표의 무게라고 한다. 투표 가치 격차는 모든 선거구의 한 표의 무게 중 최댓값을 최솟값으로 나눈 값으로 정의된다.
최근 들어 "투표 가치 격차"의 값이 심각한 사회 문제가 되고 있다. 당신은 이 값을 가능한 한 작게 만들어야 한다.
JOI 왕국의 주 정보와 대표의 수가 주어질 때, 투표 가치 격차의 값이 가능한 한 작아지도록 주를 선거구로 나누는 방법을 정하라.
입력
다음 데이터를 표준 입력에서 읽는다.
- 첫째 줄에는 네 개의 정수 H, W, N, K가 공백으로 구분되어 주어진다. H는 JOI 왕국 지도의 높이, W는 너비, N은 주의 수, K는 대표의 수이다.
- 다음 H개 줄에는 각각 W개의 정수가 공백으로 구분되어 주어진다. i번째 줄(1 ≤ i ≤ H)의 j번째 정수(j ≤ j ≤ W)는 Sij(1 ≤ Sij ≤ N)이다. 이는 위에서 i번째 행, 왼쪽에서 j번째 열에 있는 칸이 Sij번째 주에 속한다는 뜻이다.
- 다음 N개 줄 중 i번째 줄(1 ≤ i ≤ N)에는 i번째 주의 유권자 수 Pi가 주어진다.
출력
주를 선거구로 나누는 방법을 N개 줄에 출력한다. 출력의 i번째 줄(1 ≤ i ≤ N)에는 i번째 주가 속하는 선거구의 번호를 나타내는 정수를 출력한다.
제한
- 1 ≤ H ≤ 200
- 1 ≤ W ≤ 200
- 1 ≤ N ≤ 10 000
- 1 ≤ K ≤ N
- 1 ≤ Pi ≤ 100 000 (1 ≤ i ≤ N)
- 각 주에 속한 칸들은 연결된 영역을 이룬다.
힌트
이 예에서 JOI 왕국의 모양은 다음과 같다.
각 주의 유권자 수는 3, 5, 7, 10이다. 이 예시 출력에서 주는 다음과 같이 선거구로 나뉜다.
- 선거구 1 : 1번 주와 3번 주
- 선거구 2 : 2번 주
- 선거구 3 : 4번 주
각 선거구의 유권자 수는 10, 5, 10이다. 각 선거구의 한 표의 무게는 0.1, 0.2, 0.1이다. 따라서 투표 가치 격차는 0.2/0.1 = 2이다. X = 1.5, Y = 3이라면 ((3−2)/(3−1.5))2 × 100 = 44.4444444444···이고, 이 출력은 44.4444444444···점의 가치가 있다.
이 예시 입력에서 다음 분할은 선거구 2가 연결된 영역을 이루지 않으므로 허용되지 않는다.
- 선거구 1 : 1번 주
- 선거구 2 : 2번 주와 4번 주
- 선거구 3 : 3번 주