Задача A. Пасхалия ≡

Условие

Для вычисления даты Пасхи используется несложный математический алгоритм. Впервые он был предложен немецким математиком Карлом Гауссом (и носит его имя) в 1800 году.

Для определения даты Православной пасхи необходимо:

1. Разделить номер года на 19 и определить остаток от деления a.

2. Разделить номер года на 4 и определить остаток от деления b.

3. Разделить номер года на 7 и определить остаток от деления c.

4. Разделить сумму 19a + 15 на 30 и определить остаток d.

5. Разделить сумму 2b + 4c + 6d + 6 на 7 и определить остаток e.

6. Определить сумму f = d + e.

7а (по старому стилю). Если f ≤  9, то Пасха будет праздноваться (22 + f) марта; если f > 9, то Пасха будет праздноваться (f - 9) апреля.

7б (по новому стилю в XX—XXI веках). Если f ≤  26, то Пасха будет праздноваться (4 + f) апреля; если f > 26, то Пасха будет праздноваться (f - 26) мая.

По номеру года n текущего века определите дату пасхи по новому стилю.

Формат входных данных

Единственная строка входного файла содержит натуральное число n — номер года.

Формат выходных данных

Выведите одну строку — дату православной Пасхи по новому стилю в формате "число месяц" через пробел (число без ведущего нуля, месяц — April или May).

Ограничения

2000 ≤ n ≤ 2099

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

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

2023

16 April

Задача B. Буква W ≡

Условие

Евгений нарисовал на координатной плоскости красивую букву W из четырех отрезков. Отрезки расположены под углом в 45 градусов к линиям координатной сетки. Длины первого и четвертого отрезков равны, также равны длины второго и третьего отрезков, если считать слева направо. Длина первого отрезка в два раза больше второго. Все концы отрезков располагались в точках с целочисленными координатами.

Но тут пришёл Дима и стёр два отрезка из четырех. Помогите Евгению по координатам концов сохранившихся отрезков восстановить координаты концов стёртых отрезков.

Формат входных данных

В четырех строках входного файла расположены два целых числа, записанных через пробел: x_i и y_i — координаты концов сохранившихся отрезков. Отрезки перечислены слева направо, концы отрезков тоже перечислены слева направо.

Формат выходных данных

В четырех строках в том же формате и в том же порядке выведите координаты концов стёртых отрезков.

Ограничения

 − 3000 ≤ x_i, y_i ≤ 3000

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

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

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

10 5
14 1
16 3
18 1

14 1
16 3
18 1
22 5

-4 2
-2 0
-2 0
-1 1

-1 1
0 0
0 0
2 2

Задача C. Биатлон ≡

Условие

Чем заняться зимой? Только спорт, только биатлон! Лыжня и мишени, скорость и меткость, гонка и победы — вот выбор, который давно сделал Артём! Естественно, для достижения успеха необходимо много и усиленно тренироваться, чем юный спортсмен и занимается каждый день.

Для отработки техники стрельбы биатлонисты из команды Артёма использует лазерный тир, оснащенный по последнему слову техники. Всего в тире нечётное число мишеней n, расположенных горизонтально в один ряд. Радиус каждой мишени равен r, расстояние между ними равно d. Спортсмен производит k выстрелов. Для определения результата стрельбы используется система координат. Точкой начала координат определен центр средней мишени, также известны координаты попадания каждого выстрела. Компьютерная система автоматически распознает попадания по мишеням и сообщает спортсменам итоговый результат. К сожалению, именно сегодня в результате короткого замыкания жесткий диск с программным обеспечением тира вышел из строя... Вам, как самому известному программисту, предложено по координатам мишеней и результатам выстрелов написать программу, определяющую количество поражённых мишеней. Справитесь?

Формат входных данных

Первая строка входного файла содержит четыре натуральных числа, записанных через пробел: n, r, d и k. В следующих k строках через пробел расположены два целых числа x_i, y_i — координаты попадания в плоскость мишеней i-го выстрела. Гарантируется нечетность n.

Формат выходных данных

Выведите одно неотрицательное целое число - количество различных поражённых мишеней. Мишень считается поражённой, если расстояние от попадания до центра мишени не больше r. Поражённая несколько раз одна и та же мишень при подсчете учитывается один раз.

Ограничения

1 ≤ n, r, d, k ≤ 10⁵

 − 10¹² ≤ x_i, y_i ≤ 10¹²

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n = 1, получат не менее 10 баллов.

Решения, верно работающие при n = 3, получат не менее 20 баллов.

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

В примере дано три мишени радиуса 3 на расстоянии 2 друг от друга. Произведено пять выстрелов, поражены все три мишени (дважды поражена правая мишень, но она учитывается один раз).

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

3 3 2 5
11 0
-8 3
3 4
-2 -1
6 2

3

Задача D. Бахча ≡

Условие

Змеи щурят глаза на песке перегретом,

Тополя опадают. Но в травах густых

Тяжело поднимаются жарким рассветом

Перезревшие солнца обветренных тыкв.

В них накопленной силы таится обуза —

Плодородьем добротным покой нагружён,

И изранено спелое сердце арбуза

Беспощадным и острым казацким ножом.

...

Павел Васильев, "Бахча под Семипалатинском", 1929 г.

На лето родители отправили Павла к бабушке помогать ей выращивать на бахче арбузы. Чтобы они выросли большими и вкусными, требуется поливать растения каждый день (на рассвете!), что и было поручено мальчику. Если арбуз был полит, он вырастает на один килограмм (а если не был, то остаётся прежнего размера) за каждый день.

Сам огород представляет собой прямоугольную сетку из n строк и m столбцов, в каждой ячейке которой растёт арбуз, изначально имеющий массу 0 килограмм. Павел привык к богемному образу жизни и очень не любит работать, поэтому в i-й день из всех d, что он будет гостить у бабушки, планирует поливать только арбузы, лежащие на пересечении первых x_i строк и первых y_i столбцов.

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

Формат входных данных

Первая строка входного файла содержат три натуральных числа n, m и d — размер огорода (количество строк и столбцов) и время пребывания Павла у бабушки. Далее в d строках через пробел расположено по 2 натуральных числа x_i и y_i, обозначающих количество строк и столбцов, арбузы в которых были политы мальчиком в день номер i. Уточним, что эти данные упорядочены по дням, т.е. сначала идёт пара чисел x₁, y₁, затем x₂, y₂ и так далее. Отметим отдельно, что бабушка пронумеровала все строки и столбцы в огороде, и Павел всегда поливает именно x_i первых строк и y_i первых столбцов.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

Формат выходных данных

Выведите одно неотрицательное целое число — ответ на вопрос задачи.

Ограничения

1 ≤ x_i ≤ n ≤ 10⁹

1 ≤ y_i ≤ m ≤ 10⁹

1 ≤ d ≤ 10⁵

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, правильно работающие, когда произведение чисел n, m и d не превосходит 10⁶, будут оцениваться в 50 баллов.

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

Размер огорода 4 × 5, Павел проведёт у бабушки 3 дня. Смотри рисунок.

Хотя бы один раз политы 9 арбузов. Не политыми ни разу останутся 11 арбузов.

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

4 5 3
2 3
1 4
4 1

11

Задача E. На Парнас! ≡

Условие

Здесь продают билеты на Парнас,

Здесь нервничает очередь у касс:

 — Последний кто? Молчат, последних нету...

Фронтовики, толкучка не про нас,

Локтями грех орудовать поэту!

...

Юлия Друнина, "Здесь продают билеты на Парнас", 1964 г.

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

Формат входных данных

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

Формат выходных данных

Выведите одно слово — имя поэта, стоящего последним в самой короткой очереди. Если подходящих ответов несколько — выведите лексикографически наименьшее.

Ограничения

1 ≤ n ≤ 10⁵

Длина имени любого поэта не превышает 10.

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

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

В первом примере восемь поэтов составили две очереди в кассы (смотри схему). В одной из них пять человек, в другой — всего три. Юле выгоднее занять очередь за Маяковским.

Во втором примере две очереди равной длины. Из двух имён (a и d) выбираем лексикографически наименьшее.

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

8
Pushkin Chukovsky
Lermontov Yesenin
Nekrasov Pushkin
Chukovsky Cashbox
Mayakovsky Lermontov
Svetlov Nekrasov
Tsvetayeva Svetlov
Yesenin Cashbox

Mayakovsky

4
a b
b Cashbox
c Cashbox
d c

a