Mars Elections

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Java

The elections established by the Mars colony are held every 4 years. On this planet, elections determine the number of seats won by each party. The seats won are proportional to the percentage of votes they received, rounded down to the nearest seat. The seats that remain from rounding are distributed to the parties that won the largest fraction of a seat. The party with the biggest fractional seat is given one first, then the second and so on. This is repeated until there are no seats left. Using this process, determine how many seats each party would receive.

Input

The first line of input is an integer no greater then 1 million representing the total number of seats available.
The next line of input is an integer no greater then 100, n, representing the total number of parties in the election.
The next n lines is an integer no greater then 1 million representing the number of votes that party received.

Output

In order of the parties that appeared, print how many seats that party won on a new line.

Sample Input

20
3
240
315
420

Sample Output

5
6
9

Comments

There are no comments at the moment.