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

Условие

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

Так, последовательность ()(()) является правильной скобочной последовательностью, потому что она может, например, встречаться в выражении (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

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

Условие

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

Для подготовки к чемпионату мира по футболу 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

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

Условие

К 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

Задача D. Почта ≡

Условие

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

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

IT-отдел городской почты разработал кольцевой маршрут, проходящий через все почтовые отделения. Все улицы в городе P с односторонним движением. Необходимо выбрать почтовое отделение для размещения логистического центра, куда будет поступать вся городская корреспонденция перед её отправкой на Е-мобиле по маршруту. Из-за пробок скорость движения на участках маршрута между почтовыми отделениями зависит от времени суток. Размещение логистического центра считается оптимальным, если после отъезда из него в нулевой момент времени Е-мобиль развезёт корреспонденцию и возвратится в логистический центр как можно раньше. Время разгрузки корреспонденции пренебрежимо мало.

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

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

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

В следующих строках описаны N участков маршрута между почтовыми отделениями. Каждое описание содержит три строки:

• в первой строке описания задаётся целое положительное число d_i — длина данного участка (d_i ≤ 10⁹), а также целое неотрицательное число E_i — количество отрезков времени, в течение каждого из которых скорость движения Е-мобиля постоянна;
• во второй строке даны целые положительные числа t_i,j (1 ≤ j ≤ E_i, 0 < t_i,1 < … < t_i,Ei ≤ 10⁹) — значения моментов времени, в которые изменяется скорость движения. Если соответствующее E_i равно нулю, то эта строка — пустая;
• в третьей строке целые положительные числа v_j – скорости на полуинтервале времени [t_i,j−1, t_i,j), где 1 ≤ j ≤ E_i+1, считается, что t_i,0 = 0, t_i,Ei+1 = +inf.

Все числа в строках разделяются одним пробелом.

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

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

2
3 2
1
1 2
4 2
2
3 1

2 2.833333

2
2 1

2
2 1

2

1 2.000000

Задача E. Парк аттракционов ≡

Условие

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

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

Время перемещения участников между автоматами, а также между автобусом и павильоном считается равным нулю. Каждый из участников в любой момент времени может как играть на автомате, так и ждать своей очереди, например, гуляя по парку. Для каждого из M (M ≤ N) автоматов известно время игры на нём t_i (1 ≤ i ≤ M). Прервать начатую игру на автомате невозможно. Автобус привозит всех участников олимпиады в парк одновременно в нулевой момент времени.

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

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

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

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

2 1
2

4

1 0

1 2

3 2
2 1

6

1 0
2 2

1 2
2 4

2 0
1 4

Задача F. Велогонка ≡

Условие

Велосипедисты, участвующие в шоссейной гонке, в некоторый момент времени, который называется начальным, оказались в точках, удалённых от места старта на x₁, x₂, …, x_n метров (n – общее количество велосипедистов). Каждый велосипедист двигается со своей постоянной скоростью v₁, v₂, …, v_n метров в секунду. Все велосипедисты двигаются в одну и ту же сторону.

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

Требуется написать программу, которая по заданному количеству велосипедистов n, заданным начальным положениям велосипедистов x₁, x₂, …, x_n и их скоростям v₁, v₂, …, v_n, вычислит момент времени t, в который расстояние l между лидирующим и замыкающим велосипедистом будет минимальным.

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

Первая строка входного файла содержит целое число n – количество велосипедистов.

В последующих n строках указаны по два целых числа: x_i – расстояние от старта до i-го велосипедиста в начальный момент времени (0 ≤ xi ≤ 10⁷) и v_i – его скорость (0 ≤ v_i ≤ 10⁷).

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

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

Числа t и l должны иметь абсолютную или относительную погрешность не более 10⁻⁶, что означает следующее. Пусть выведенное число равно x, а в правильном ответе оно равно y. Ответ будет считаться правильным, если значение выражения |x − y| / max(1, |y|) не превышает 10⁻⁶.

Ограничения

2 ≤ n ≤ 10⁵

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

3
0 40
30 10
40 30

1 30

5
90 100
100 70
100 70
110 60
120 35

0.5 5.000000000000

Задача G. Сад пермского периода ≡

Условие

Оранжерея “Сад пермского периода” представляет собой прямоугольный участок для выращивания растений пермского периода. Оранжерея была разбита дорожками на квадраты. В центре каждого квадрата посажено одно растение. Размер квадрата зависит от корневой системы растения.

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

Введем декартову прямоугольную систему координат, начало которой совмещено с левым нижним углом оранжереи. Ось Ox направлена вдоль нижней границы участка, ось Oy – вдоль левой. Изначально дорожки были проложены параллельно осям координат. Единичный отрезок удалось выбрать так, что координаты углов каждого из квадратов оказались целыми.

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

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

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

Ограничения

W, H ≤ 10¹²;

N ≤ 2 × 10⁵;

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

4 6 3
1 1
3 1
2 4

2
2
4

8 8 10
4.5 7.5
5.5 7.5
2 6
4.5 6.5
7 7
5 5
6 2
7 5
2 2
5.5 6.5

1
1
4
1
2
2
4
2
4
1