Задача A. Соревнование картингистов ≡

Условие

После очередного этапа чемпионата мира по кольцевым автогонкам на автомобилях с открытыми колесами Формула-А гонщики собрались вместе в кафе, чтобы обсудить полученные результаты. Они вспомнили, что в молодости соревновались не на больших болидах, а на картах – спортивных автомобилях меньших размеров.

Друзья решили выяснить победителя в одной из гонок на картах. Победителем гонки являлся тот гонщик, у которого суммарное время прохождения всех кругов трассы было минимальным.

Поскольку окончательные результаты не сохранились, то каждый из N участников той гонки вспомнил и выписал результаты прохождения каждого из M кругов трассы. К сожалению, по этой информации гонщикам было сложно вычислить победителя той гонки. В связи с этим они попросили сделать это вас.

Требуется написать программу, которая вычислит победителя гонки на картах, о которой говорили гонщики.

Формат входного файла

Первая строка входного файла содержит два целых числа N, M.

Последующие 2 × N строк описывают прохождение трассы каждым из участников. Описание прохождения трассы участником состоит из двух строк:

• Первая строка содержит имя участника с использованием только латинских букв (строчных и заглавных). Имена всех участников различны, строчные и заглавные буквы в именах различаются.
• Вторая строка содержит M положительных целых чисел t_{i, j}, где каждое число — это время прохождения данным участником каждого из M кругов трассы.

Формат выходного файла

В выходной файл необходимо вывести имя победителя гонки на картах. Если победителей несколько, требуется вывести имя любого из них.

Ограничения

1 ≤ N, M ≤ 100, 1 ≤ t_{i, j} ≤ 1000

Длина каждой строки не превышает 255 символов

Примеры тестов

5 3
Sumaher
2 1 1
Barikelo
2 1 2
Olonso
1 2 1
Vasya
1 1 1
Fedya
1 1 1

Fedya

Задача B. Дипломы ≡

Условие

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось N дипломов, причем, как оказалось, все они имели одинаковые размеры: W — в ширину и H — в высоту.

Сейчас Петя учится в одном из лучших российских университетов и живет в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить ее к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещен строго в прямоугольнике размером W на H. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек.

Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов.

Система оценивания

Решения, правильно работающие только при W, H, N ≤ 1000, будут оцениваться в 40 баллов.

Формат входного файла

Входной файл содержит три целых числа: W, H, N

Формат выходного файла

В выходной файл необходимо вывести ответ на поставленную задачу.

Ограничения

1 ≤ W, H, N ≤ 10⁹

Примеры тестов

2 3 10

9

Задача C. Булева функция ≡

Условие

Недавно на уроке информатики ученики одного из классов изучили булевы функции. Напомним, что булева функция f сопоставляет значениям двух булевых аргументов, каждый из которых может быть равен 0 или 1, третье булево значение, называемое результатом. Для учеников, которые выразили желание более подробно изучать эту тему, учительница информатики на дополнительном уроке ввела в рассмотрение понятие цепного вычисления булевой функции f.

Если задана булева функция f и набор из N булевых значений a₁, a₂, …, a_N, то результат цепного вычисления этой булевой функции определяется следующим образом:

• если N = 1, то он равен a₁
• если N > 1, то он равен результату цепного вычисления булевой функции f для набора из (N−1) булевого значения f(a₁, a₂), a₃, …, a_N, который получается путем замены первых двух булевых значений в наборе из N булевых значений на единственное булево значение — результат вычисления функции f от a₁ и a₂.

Например, если изначально задано три булевых значения: a₁ = 0, a₂ = 1, a₃ = 0, а функция f — ИЛИ (OR), то после первого шага получается два булевых значения — (0 OR 1) и 0, то есть, 1 и 0. После второго (и последнего) шага получается результат цепного вычисления, равный 1, так как 1 OR 0 = 1.

В конце дополнительного урока учительница информатики написала на доске булеву функцию f и попросила одного из учеников выбрать такие N булевых значений a_i, чтобы результат цепного вычисления этой функции был равен единице. Более того, она попросила найти такой набор булевых значений, в котором число единиц было бы как можно большим.

Требуется написать программу, которая решала бы поставленную учительницей задачу.

Пояснения к примерам

• В первом примере процесс вычисления цепного значения булевой функции f происходит следующим образом: 1011 → 111 → 01 → 1
• Во втором примере вычисление цепного значения булевой функции f происходит следующим образом: 11111 → 0111 → 111 → 01 → 1
• В третьем примере получить цепное значение булевой функции f, равное 1, невозможно.

Система оценивания

Формат входного файла

Первая строка входного файла содержит одно натуральное число N

Вторая строка входного файла содержит описание булевой функции в виде четырех чисел, каждое из которых — ноль или единица. Первое из них есть результат вычисления функции в случае, если оба аргумента — нули, второе — результат в случае, если первый аргумент — ноль, второй — единица, третье — результат в случае, если первый аргумент — единица, второй — ноль, а четвертый — в случае, если оба аргумента — единицы.

Формат выходного файла

В выходной файл необходимо вывести строку из N символов, определяющих искомый набор булевых значений a_i с максимально возможным числом единиц. Если ответов несколько, требуется вывести любой из них. Если такого набора не существует, выведите в выходной файл фразу No solution.

Ограничения

2 ≤ N ≤ 10⁵

Примеры тестов

4
0110

1011

5
0100

11111

6
0000

No solution

Задача D. Кольцевая автодорога ≡

Условие

К 2110 году город Флэтбург, являясь одним из крупнейших городов мира, не имеет обходной автомагистрали, что является существенным препятствием для его развития как крупнейшего транспортного центра мирового значения. В связи с этим еще в 2065 году при разработке Генерального плана развития Флэтбурга была определена необходимость строительства кольцевой автомобильной дороги.

В Генеральном плане также были обозначены требования к этой дороге. Она должна соответствовать статусу кольцевой — иметь форму окружности. Кроме этого, четыре крупные достопримечательности Флэтбурга должны быть в одинаковой транспортной доступности от дороги. Это предполагается обеспечить тем, что они будут находиться на равном расстоянии от нее. Расстоянием от точки расположения достопримечательности до дороги называется наименьшее из расстояний от этой точки до некоторой точки, принадлежащей окружности автодороги.

Дирекция по строительству города Флэтбурга, ответственная за постройку кольцевой автодороги, решила привлечь передовых программистов для выбора оптимального плана постройки дороги.

Требуется написать программу, которая вычислит число возможных планов постройки кольцевой автомобильной дороги с соблюдением указанных требований и найдет такой план, для которого длина дороги будет минимальной.

Формат входного файла

Входной файл содержит четыре строки. Каждая из них содержит по два целых числа: x_i и y_i — координаты места расположения достопримечательности. Первая строка описывает первую достопримечательность, вторая — вторую, третья — третью, четвертая — четвертую. Никакие две достопримечательности не находятся в одной точке.

Формат выходного файла

В первой строке выходного файла требуется вывести число возможных планов постройки кольцевой автомобильной дороги. Если таких планов бесконечно много, необходимо вывести в первой строке выходного файла слово Infinity.

На второй строке требуется вывести координаты центра дороги минимальной длины и ее радиус. Если существует несколько разных способов построения дороги минимальной длины, необходимо вывести координаты центра и радиус любой из них. Координаты центра и радиус дороги должны быть выведены с точностью не хуже 10⁻⁸ и не превосходить по абсолютной величине 10⁹.

Ограничения

−100 ≤ x_i, y_i ≤ 100

Примеры тестов

0 0
0 1
1 0
2 2

7
1.5 0.5 1.14412281

0 0
0 1
1 0
1 1

Infinity
0.5 0.5 0.0