Задача A. Антон сводит старые счеты ≡

Условие

На чердаке у бабушки Антон нашел пару старых счёт. Первые счёты изначально имели n₁ спиц, на каждой из которых располагалось по m₁ костяшек, вторые — соответственно n₂ спиц по m₂ костяшек. Время не пощадило вычислительные приспособления, и часть спиц и костяшек оказалось утрачено.

Антон хочет знать, возможно ли починить какие-нибудь счёты, воспользовавшись спицами и костяшками других счёт (все костяшки и спицы — одинаковые).

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

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

Входной файл содержит целые числа n₁ m₁ n₂ m₂, за которыми следует n₁ чисел p_i — количество оставшихся костяшек на i−й спице первых счёт, затем n₂ чисел q_i — количество оставшихся костяшек на i−й спице первых счёт. Если спица отсутствует, вместо соответствующего количества указывается число −1.

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

Выходной файл должен содержать единственное целое число:

• 0, если ни одни счёты починить нельзя;
• 1, если возможно починить только первые счёты;
• 2, если возможно починить только вторые счёты;
• 12, если можно починить либо те, либо другие (не обязательно одновременно).

Ограничения

1 ≤ n₁, n₂, m₁, m₂ ≤ 2000; −1 ≤ p_i ≤ m₁; −1 ≤ q_i ≤ m₂.

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

1 10 1 5
10
5

12

2 2 3 3
1
-1
0
2
3

1

Задача B. Марфа Геннадьевна и часы ≡

Условие

Наблюдая за движением стрелок часов, Марфа Геннадьевна размышляла о природе времени — насколько быстро оно течёт! Совсем недавно она была молодая, а теперь уже далеко в возрасте. Она вспомнила выражение Гераклита: "всё течёт, всё меняется".

И тут неожиданно для себя Марфа Геннадьевна обратила внимание, что угол между часовой и минутной стрелками тоже постоянно изменяется, и это происходит периодично: минутная стрелка то приближается к часовой, то отдаляется от неё, и дальше всё повторяется. Марфа Геннадьевна подумала: что, если всё в нашем мире происходит так же периодично, как и движение стрелок часов?

Будучи по образованию специалистом по естественным наукам, а не философом, Марфа Геннадьевна решила провести вычислительный эксперимент и построить график внутреннего угла между стрелками. Но для этого ей понадобилась помощь программиста. Марфа Геннадьевна попросила своего знакомого Лёню написать программу для построения графика. Лёня успешно справился с задачей, но не до конца. Он написал программу для построения графика, но теперь ему нужен модуль, который вычислит функцию угла между стрелками.

Марфа Геннадьевна и Лёня просят вас им помочь. Напишите программу, принимающую на вход текущее время и вычисляющую угол между стрелками в градусах.

Марфа Геннадьевна использует стандартный 12-часовой циферблат. Число секунд в текущем времени принять равным 0.

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

Входной файл содержит целые числа H M — часы и минуты.

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

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

Ограничения

0 ≤ H ≤ 23, 0 ≤ M ≤ 59.

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

21 45

22.5000

12 0

0.0000

7 30

45.0000

10 15

142.5000

12 30

165.0000

Задача C. Прямой кёрлинг ≡

Условие

Кёрлинг (англ. curling, от скотс. curr) — командная спортивная игра на ледяной площадке. Участники двух команд поочерёдно пускают по льду специальные тяжёлые гранитные снаряды (камни) в сторону размеченной на льду мишени (дома).

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

На поле введена прямоугольная система координат. Вася всегда запускает камень из начала координат. Дом находится в точке с координатами (L, 0). Каждый камень представляет собой окружность радиуса R. Перед броском на поле имеется N камней. Центр i-ого камня находится в точке с координатами (x_i, y_i).

Рекомендуется рассмотреть частичные решения

1. N = 1

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

Входной файла содержит целые числа L R N, за которыми следуют N пар целых чисел x_i y_i.

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

Выходной файл должен содержать два вещественных числа — координаты x y точки, в которой должен остановиться брошенный камень. Если вариантов ответа несколько, выведите любой из них. Ответ должен быть найден с точностью не менее 9 знаков после запятой.

Ограничения

1 ≤ N ≤ 5; 1 ≤ L, R ≤ 100, −100 ≤ x_i, y_i ≤ 100, 4 R² ≤ x2i + y2i.

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

5 1 1
4 0

3.750000000 2.165063509

Задача D. Поучительный фильм ≡

Условие

Учителю Иванову пришло указание вместо уроков отвести M учеников своего класса в кино на просмотр поучительного фильма "О пользе хорошего поведения". Учитель опасается, что тема фильма не вызовет достаточно большого интереса у школьников, и они начнут хулиганить.

Кресла в зале кинотеатра расположены в N рядов по N мест в каждом. Определим расстояние между креслами как сумму модулей разностей номеров рядов и номеров мест.

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

Рекомендуется рассмотреть частичные решения

1. M = 1
2. N ≤ 100

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

Первая строка входного файла содержит целые числа N M. Следующие N строк содержат по N символов '.' (ASCII 46) и '#' (ASCII 35) каждая, обозначающих соответственно свободное и занятое место. Ряды нумеруются от 1 до N сверху вниз, места нумеруются от 1 до N слева направо.

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

Выходной файл должен содержать целое число R — наименьшее возможное максимальное расстояние. Далее должна следовать M + 1 пара чисел — номера рядов и мест сначала для учителя, затем для учеников.

Если учеников рассадить невозможно, выведите единственное число 0. Если существует несколько оптимальных решений, выведите любое из них.

Ограничения

1 ≤ M ≤ 10⁶; 1 ≤ N ≤ 2000

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

4 8
....
..#.
....
###.

2
2 2
1 1
1 2
1 3
2 1
2 4
3 1
3 2
3 3

2 2
##
#.

0