Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |

Реализация заданного алгоритма

Олимпиадные задачи на английском языке

Олимпиадные задачи на английском языке

25/06/2012 | Лето 2012 - дорешивание (12A) |

12/07/2012 | Лето 2012 - 12 (командный) (A) |

*Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод*

Послать решение Blockly Посылки Темы Где Обсудить (2)

In the beginning of December, parliamentary elections were held in our country. Croatia is divided in
10 election regions. From each region, 14 parliamentary representatives are elected. Each of the
voters is voting for one of the few parties. After voting, the representatives are elected using the
D'Hondt (D''Ont) method.

By this method, first we select parties which gathered *at least* 5% of the votes. Number of votes of
each of the selected parties is then divided by every number from 1 to 14. In this way we assign 14
rational numbers – let's call them "scores" – to each of the parties.

First of the 14 representatives in a region is chosen from a party with the largest score. Second
representative is selected from a party with the second largest score. The third… This procedure
continues until all of the 14 places are elected. Remark: There will always be a unique way to elect the
representatives, i.e. no two scores will be equal.

Write a program that, given the total number of voters and number of votes each party gained,
determines how many politicians were elected as region representatives from each party. Some parties
have gained negligible number of votes and will not be in the input – that is the reason that the total
number of voters might not be equal to the sum of list votes in the input.

First line of input contains a positive integer `X` (`1\ ≤\ X\ ≤\ 2\ 500\ 000`), total number of voters in the
region. Second line of input contains a positive integer `N` (`0\ ≤\ N\ ≤\ 10`), number of parties we are
considering. Next `N` lines contain two positive integers divided by a single space: party identifier
(capital letter of English alphabet) and a positive integer `G` (`0\ ≤\ G\ ≤\ 250\ 000`), number of votes gained
by that party.

Output is consisted of number of lines equal to **the number of parties which had at least 5% of the
votes**. For each of these parties, print a party identifier and a number of parliamentary representatives
elected from that party. Lines should be sorted by identifiers, alphabeticaly.

Sample Input #1

235217 3 A 107382 C 18059 B 43265

Sample Output #1

A 9 B 4 C 1

Sample Input #2

245143 4 F 14845 A 104516 B 52652 C 14161

Sample Output #2

A 8 B 4 C 1 F 1

Sample Input #3

206278 5 D 44687 A 68188 C 7008 B 48377 G 9665

Sample Output #3

A 6 B 4 D 4