Vote-Value Disparity 1

A national election will be held in the JOI kingdom. The kingdom has $N$ provinces.

The map is an $H \times W$ grid. Each cell connects to neighbors by sharing a side. The grid is partitioned into $N$ connected provinces. Province $i$ has $P_i$ voters.

You must divide the provinces into $K$ electoral districts to elect $K$ representatives. Each district contains at least one province, and the cells in a district form a connected region. Cells connect only through shared sides, not shared corners.

The weight of a single vote in a district is $1 / \text{(number of voters in that district)}$. The vote-value disparity is the maximum such weight divided by the minimum. Minimize this disparity.

The first line contains $H$, $W$, $N$, and $K$.

Each of the next $H$ lines has $W$ integers $S_{ij}$, the province id of each cell.

Each of the next $N$ lines has $P_i$, the number of voters in province $i$.

Print $N$ lines. Line $i$ is the district number ($1$ to $K$) for province $i$.

• $1 \le H \le 200$
• $1 \le W \le 200$
• $1 \le N \le 10\,000$
• $1 \le K \le N$
• $1 \le P_i \le 100\,000$
• Each province forms a connected region on the grid.