IZBORI - IZBORI
English | Vietnamese |
It is election time. V voters attend the election, each casting their vote for one of N political parties. M officials will be elected into the parliament.
The conversion from votes to parliament seats is done using the D'Hondt method with a 5% threshold. More precisely, suppose that the parties are numbered 1 through N and that they receive V1, V2, ..., VN votes. Parliament seats are allocated as follows:
- All parties that receive strictly less than 5% of V votes are erased from the list of parties.
- The parliament is initially empty i.e. every party has zero seats allocated.
- For each party P, the quotient QP=VP/(SP+1) is calculated, where VP is the total number of votes received by party P, and SP is the number of seats already allocated to party P.
- The party with the largest quotient QP is allocated one seat. If multiple parties have the same largest quotient, the lower numbered party wins the seat.
- Repeat steps 3 and 4 until the parliament is full. The votes are being counted and only part of the V votes has been tallied. It is known how many votes each party has received so far.
Write a program that calculates for each party, among all possible outcomes of the election after all V votes are counted, the largest and smallest number of seats the party wins.
Input
The first line contains the integers V, N and M (1 ≤ V ≤ 10,000,000, 1 ≤ N ≤ 100, 1 ≤ M ≤ 200), the numbers of votes, parties and seats in the parliament.
The second line contains N integers – how many votes (of those that have been counted) each party got. The sum of these numbers will be at most V.
Output
On the first line output N integers separated by spaces – the largest number of seats each party can win.
On the second line output N integers separated by spaces – the smallest number of seats each party can win.
Example
Input: 20 4 5 4 3 6 1 Output: 3 3 3 2 1 0 1 0
Input: 100 3 5 30 20 10 Output: 4 3 3 1 1 0
In the first example, 14 votes have been tallied and 6 are yet to be counted. To illustrate one possible outcome, suppose that the first party receives 2 of those 6 votes, the second none, the third 1 vote and the fourth 3 votes. The parties' totals are 6, 3, 7 and 4 votes. All parties exceeded the 5% threshold. Seats are allocated as follows:
- The quotients are initially 6/1, 3/1, 7/1 and 4/1; the largest is 7/1 so party 3 wins a seat.
- The quotients are 6/1, 3/1, 7/2 and 4/1; the largest is 6/1 so party 1 wins a seat.
- The quotients are 6/2, 3/1, 7/2 and 4/1; the largest is 4/1 so party 4 wins a seat.
- The quotients are 6/2, 3/1, 7/2 and 4/2; the largest is 7/2 so party 3 wins a seat.
- The quotients are 6/2, 3/1, 7/3 and 4/2; parties 1 and 2 are tied with quotients 6/2 and 3/1, but party 1 is lower numbered so it wins the last seat.
In this outcome, the numbers of seats won by the parties are 2, 0, 2 and 1. Since it is possible for the second party not to win any seats, the second number on the second line of output is zero.
Added by: | Race with time |
Date: | 2009-03-29 |
Time limit: | 0.104s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Croatian Olympiad in Informatics 28.03.2009. |