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

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

03/07/2008 | Лето 2008 дорешивание (12D) |

28/07/2008 | Лето 2008 - 12 (D) |

24/07/2013 | Лето 2013-16 (командная) (D) |

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

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

Every September, the Kingdom of Loowater holds a jousting tournament.
In each of a series of event, a pair of knights attempt to knock each
other from their respective horses. The winning knight is paired
with another, while the loser is elimnated. This process continues
until all but one knight is eliminated; this knight is
declared champion.

The tournament schedule is organized so that no knight needs
to compete in more than `e` events to be champion,
for the minimum possible `e` given `k`,
the number of knights. In order to construct the
schedule, it may be necessary to identify several
knights who compete in fewer than `e` events;
these knights are said to be awarded a *bye* and
are excluded from the first round of competition.

The first round of competition involves pairing as
many knights as possible among those who are not
awarded a bye. The competition is more interesting
if the knights in each pair are as evenly matched
in ability as possible. You are to determine
which knights should be awarded a bye so as to
make the first round as interesting as possible.

Standard input consists of several test cases followed
by a line containing 0. Each
test case begins with an integer `1\ <\ k\ \ ≤\ 2500`,
the number of knights. `k` lines follow, each giving
the name and ability of a knight. The name is a string
of lower case letters not longer than 20; the ability is
a real number.

The *mismatch* between knights with abilities `a`
and `b` respectively is defined to be `(a-b)^2`.

For each test case, output the names of the knights to be given
a bye such that the sum of all mismatch values for pairs of
knights competing in the first round is minimized. If there
are several solutions, any will do.

Output an empty line between test cases.

Sample Input

3 gallahad 10 lancelot 11 mccartney 2 0

Output for Sample Input

mccartney