P8364 [COI 2009] IZBORI

There are $V$ voters voting in an election. In this election, $N$ parties participate and compete for $M$ seats in the parliament. Assume the parties are numbered from $1$ to $N$, and they receive $v_1, v_2, \cdots, v_n$ votes respectively. Seats are allocated as follows: 1. Any party that gets less than $5\%$ of the votes is directly disqualified from further seat allocation. 2. At the beginning, no seats are reserved for any party. 3. For each party, compute $Q_p = V_p \div (S_p + 1)$, where $V_p$ is the total votes received by the party, and $S_p$ is the number of seats already allocated to that party. 4. The party with the largest $Q_p$ gets one seat. (If tied, the party with the smaller index gets it.) 5. Repeat steps 3 and 4 until all seats are allocated. Now some ballots have been counted, and the current vote counts of the parties are known. Write a program to determine, over all possible situations, the maximum or minimum number of seats each party can obtain.

The first line contains three positive integers $V, N, M$. The second line contains $N$ positive integers, the current vote counts of each party. It is guaranteed that their sum does not exceed $V$.

Output $N$ integers on the first line, the maximum possible number of seats each party can obtain. Output $N$ integers on the second line, the minimum possible number of seats each party can obtain.

Correctly outputting the first line earns $20\%$ of the score. Correctly outputting the second line earns $80\%$ of the score. Constraints: $1 \le V \le 10^7$, $1 \le N \le 100$, $1 \le M \le 200$. Translated by ChatGPT 5