Задача 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. Газон Ивана ≡

Условие

Фермер Иван с юности следит за своим газоном. Газон можно считать плоскостью, на которой в каждой точке с целыми координатами растет один пучок травы.

В одно из воскресений Иван воспользовался газонокосилкой и постриг некоторый прямоугольный участок газона. Стороны этого участка параллельны осям координат, а две противоположные вершины расположены в точках (x₁, y₁) и (x₂, y₂). Следует отметить, что пучки травы, находящиеся на границе этого прямоугольника, также были пострижены.

Довольный результатом Иван купил и установил на газоне дождевальную установку. Она была размещена в точке с координатами (x₃, y₃) и имела радиус действия струи r. Таким образом, установка начала поливать все пучки, расстояние от которых до точки (x₃, y₃) не превышало r.

Все было хорошо, но Ивана заинтересовал следующий вопрос: сколько пучков травы оказалось и пострижено, и полито в это воскресенье?

Требуется написать программу, которая позволит дать ответ на вопрос Ивана.

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

В первой строке входного файла содержатся четыре целых числа x₁ y₁ x₂ y₂. Во второй строке входного файла содержатся три целых числа x₃ y₃ r.

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

Ограничения

−10⁵ ≤ x₁, y₁, x₂, y₂, x₃, y₃ ≤ 10⁵

1 ≤ r ≤ 10⁵

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

0 0 5 4
4 0 3

14

Задача C. Скобки ≡

Условие

Юная программистка Агнесса недавно узнала на уроке информатики об арифметических выражениях. Она заинтересовалась вопросом, что случится, если из арифметического выражения удалить всё, кроме скобок. Введя запрос в своём любимом поисковике, она выяснила, что математики называют последовательности скобок, которые могли бы встречаться в некотором арифметическом выражении, правильными скобочными последовательностями.

Так, последовательность ()(()) является правильной скобочной последовательностью, потому что она может, например, встречаться в выражении (2+2):(3–(5–2)+4), а последовательности (() и ())( не являются таковыми. Легко видеть, что существует пять правильных скобочных последовательностей, состоящих ровно из шести скобок (по три скобки каждого типа — открывающих и закрывающих): ((())), (()()), (())(), ()(()) и ()()().

Агнесса заинтересовалась простейшими преобразованиями правильных скобочных последовательностей. Для начала Агнесса решила ограничиться добавлением скобок в последовательность. Она очень быстро выяснила, что после добавления одной скобки последовательность перестаёт быть правильной, а вот добавление двух скобок иногда сохраняет свойство правильности. Например, при добавлении двух скобок в различные места последовательности ()() можно получить последовательности (()()), (())(), ()(()) и ()()(). Легко видеть, что при любом способе добавления двух скобок с сохранением свойства правильности одна из новых скобок должна быть открывающей, а другая — закрывающей.

Агнесса хочет подсчитать количество различных способов добавления двух скобок в заданную правильную скобочную последовательность так, чтобы снова получилась правильная скобочная последовательность. К сожалению, выяснилось, что это количество может быть в некоторых случаях очень большим. Агнесса различает способы получения последовательности по позициям добавленных скобок в полученной последовательности. Например, даже при добавлении скобок в простейшую последовательность () можно получить другую правильную скобочную последовательность семью способами: ()(), (()), (()), (()), (()), ()(), ()().

Таким образом, если в полученной последовательности добавленная открывающая скобка стоит в позиции i, а добавленная закрывающая — в позиции j, то два способа, соответствующие парам (i 1, j 1) и (i 2, j 2), считаются различными, если i 1 ≠ i 2 или j 1 ≠ j 2.

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

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

Подзадача 1 (40 баллов): Величина n (количество скобок каждого типа) не превосходит 50.

Подзадача 2 (30 баллов): Величина n (количество скобок каждого типа) не превосходит 2500.

Подзадача 3 (30 баллов): Величина n (количество скобок каждого типа) не превосходит 50 000.

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

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

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

()

7

()()

17

(())

21

Задача D. Школа олимпийского резерва ≡

Условие

Внимание! Используется лишь часть тестов из оригинального набора!

Для подготовки к чемпионату мира по футболу 2018 года создается школа олимпийского резерва. В нее нужно зачислить M юношей 1994-1996 годов рождения. По результатам тестирования каждому из N претендентов был выставлен определенный балл, характеризующий его мастерство. Все претенденты набрали различные баллы. В составе школы олимпийского резерва хотелось бы иметь A учащихся 1994 г.р., B – 1995 г.р. и C – 1996 г.р. (A + B + C = M). При этом минимальный балл зачисленного юноши 1994 г.р. должен быть больше, чем минимальный балл зачисленного 1995 г.р., а минимальный балл зачисленного 1995 г.р. должен быть больше, чем минимальный балл зачисленного 1996 г.р. Все претенденты, набравшие балл больше минимального балла для юношей своего года рождения, также должны быть зачислены.

В базе данных для каждого претендента записаны год его рождения и тестовый балл. Требуется определить, сколько нужно зачислить юношей каждого года рождения M₉₄, M₉₅ и M₉₆ (M₉₄ + M₉₅ + M₉₆ = M), чтобы значение величины F = |M₉₄ − A| + |M₉₅ − B| + |M₉₆ − C| было минимально, все правила, касающиеся минимальных баллов зачисленных, были соблюдены, и должен быть зачислен хотя бы один юноша каждого требуемого года рождения.

В первом примере на первом наборе ответ не существует, потому что нельзя пригласить хотя бы одного юношу 1995 г.р. Во втором наборе ответ существует и единственный, в третьем – нельзя выполнить правило относительно минимальных баллов.

Во втором примере правильным является также ответ 2 2 2 2.

Подзадача 1 (25 баллов): K = 1; N ≤ 100; каждый претендент характеризуется своим баллом от 1 до N.

Подзадача 2 (25 баллов): Сумма значений N по всем тестовым наборам не превосходит 10 000, каждый претендент характеризуется своим баллом от 1 до 10⁹.

Подзадача 3 (25 баллов): Сумма значений N по всем тестовым наборам не превосходит 100 000, каждый претендент характеризуется своим баллом от 1 до N.

Подзадача 4 (25 баллов): Сумма значений N по всем тестовым наборам не превосходит 300 000, каждый претендент характеризуется своим баллом в диапазоне от 1 до 10⁹.

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

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

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

3
1 1 1
4
1994 3
1994 4
1996 1
1996 2
1 1 1
3
1995 2
1994 3
1996 1
1 1 1
3
1994 1
1995 2
1996 3

-1
0 1 1 1
-1

1
2 3 1
7
1996 2
1994 7
1994 4
1996 1
1995 3
1994 5
1995 6

2 3 2 1

Задача E. Снова в космос ≡

Условие

К 50-летию первого пилотируемого полета в космос решено создать новый тип космического корабля многоразового использования “Восторг”. Прямоугольная часть его корпуса (далее прямоугольник) должна быть облицована квадратными термозащитными плитками разных цветов одного и того же размера. Прямоугольник состоит из r рядов по c плиток в каждом. Плитки должны образовывать заданный рисунок.

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

Главный конструктор хочет выбрать такой размер панели a × b и сдвиг s, чтобы этими панелями можно было выложить заданный рисунок, и площадь панели была минимальна.

Требуется написать программу, которая по заданному расположению плиток в прямоугольнике рассчитывает размеры минимальной по площади панели, которую можно использовать при его облицовке, а также величину сдвига вправо (0 ≤ s < b) каждого следующего ряда относительно предыдущего.

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

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

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

2 4
ABAB
ABAB

1 2 0

5 7
DCADCAD
BABBABB
ADCADCA
BBABBAB
CADCADC

2 3 1