Задача A. КрокодАвиа ≡

Условие

Аэропорты авиакомпании "КрокодАвиа" расположены в N городах по всему земному шару. Авиакомпании требуется знать расстояние в километрах от каждого аэропорта до ближайшего из оставшихся.

Считая Землю идеальным шаром, расстояние между двумя точками на поверхности можно вычислить по формуле

arccos(sin(lat₁) × sin(lat₂) + cos(lat₁) × cos(lat₂) × cos(lon₁−lon₂)) × R,

где lon₁ lat₁ — долгота и широта первой точки, lon₂ lat₂ — долгота и широта второй точки, R = 6373км — радиус Земли.

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

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

Ограничения

−180 ≤ lon_i ≤ 180

−90 ≤ lat_i ≤ 90

2 ≤ N ≤ 5000

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

2
0 0
180 0

20021.36998
20021.36998

3
-123 -12
-123 -12
0 0

0.000
0.000
13591.239

Задача B. Поезда с шушанчиками ≡

Условие

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

Старуха Шапокляк собирается украсть шушанчиков. Она знает, что успеет только на один из двух поездов, и хочет попасть на более длинный из них. Старухе удалось достать у волшебника на вертолёте M фотографий участка железной дороги, сделанных как раз в то время, когда поезда проезжали один мимо другого.

На фотографиях изображён один и тот же участок дороги, который выглядит как два горизонтальных отрезка длины W. Поезд Гены перемещается по первому отрезку слева направо, а поезд Чебурашки — по второму отрезку справа налево. Снимки расположены в хронологическом порядке, но сделаны с разными интервалами времени. На каждом снимке обязательно видны оба поезда, хотя и не обязательно целиком.

Позиции поездов на каждой фотографии заданы четырьмя числами L₁, R₁, L₂, R₂, где L₁, R₁ — расстояния от левого края снимка до левого и правого концов видимой части поезда Гены, а L₂, R₂ — аналогичные расстояния до видимой части поезда Чебурашки. Если какое-то из чисел равно 0 или W, то соответствующий поезд, возможно, попал на эту фотографию не полностью.

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

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

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

Ограничения

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

1 3
0 3 1 2

1

3 3
0 1 2 3
0 2 1 3
1 3 0 2

3

Задача C. Ответы к тесту ≡

Условие

Крокодил Гена решил поступить в университет. Для поступления ему нужно пройти тест, состоящий из Q вопросов. На каждый из них можно ответить либо "Да", либо "Нет". Количество баллов, получаемых абитуриентом за тест, равно количеству данных им правильных ответов. Все абитуриенты проходят тест с одними и теми же вопросами.

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

По этим данным Гена должен определить правильные ответы.

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

В первой строке входного файла содержатся числа P Q. Далее следует P описаний шушанчиков, по две строки на описание:

• В первой строке описываются ответы, данные шушанчиком. Они задаются строкой длинной Q, состоящей из символов + (ASCII 43) или - (ASCII 45) для ответов "Да" или "Нет" соответственно. На i-ой позиции строки находится ответ на i-ый вопрос.
• Во второй строке содержится целое число — количество баллов.

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

В выходном файле должна содержаться единственная строка, состоящая из Q символов + (ASCII 43) или - (ASCII 45) — правильные ответы к тесту. Если существует несколько вариантов правильных ответов, вывести любой из них. Так, во втором примере допустим также ответ -+++.

Ограничения

1 ≤ P ≤ 1000, 1 ≤ Q ≤ 15

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

1 2
+-
0

-+

3 4
--++
3
----
1
---+
2

+-++

Задача D. Новые чемоданы ≡

Условие

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

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

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

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

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

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

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

Если интересующая Гену покупка невозможна, то в выходном файле должна содержаться строка NO. В противном случае в первой строке выходного файла должно содержаться YES, а во второй строке — длины сторон чемоданов, которые следует приобрести, записанные через пробел в произвольном порядке. Если существует несколько решений, вывести любое из них.

Ограничения

1 ≤ N ≤ 10⁵, 1 ≤ K ≤ 1000.

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

10 5

YES
1 3

842 1

NO

98 2

YES
7 7

Задача E. Парад шушанчиков ≡

Условие

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

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

Например, если ряд задан строкой abbbccbb, Гена может поступить следующим образом: abbbccbb → abccbb → ab

Крокодил хочет добиться, чтобы в ряду осталось как можно меньше шушанчиков.

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

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

Ограничения

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

abbbccbb

ab

abbaccdd

EMPTY

aaacccmmm

acm

Задача F. Перекрашивание шушанчиков ≡

Условие

У Крокодила Гены есть N чемоданов с шушанчиками, пронумерованных от 1 до N. В чемодане с номером i находится i шушанчиков.

Главное развлечение Крокодила Гены — перекрашивание шушанчиков. Процесс перекрашивания заключается в следующем: Гена произвольно выбирает ненулевое количество шушанчиков из какого-нибудь чемодана, берет i миллилитров краски, где i — номер выбранного чемодана, и тратит её всю на выбранных шушанчиков.

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

Очевидно, что когда-нибудь Крокодил Гена перекрасит все возможные наборы шушанчиков из всех чемоданов. Вопрос лишь в том, сколько краски он на это потратит. Ответ может оказаться очень большим числом, поэтому найдите лишь его остаток от деления на заданное M.

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

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

Выведите единственное число — остаток от деления количества миллилитров краски на M.

В первом примере существует единственный набор из одного шушанчика, поэтому ответ 1. Во втором примере Гене потребуется 7 миллилитров краски (1 × 1 + 2 × 3), а остаток от деления 7 на 5 есть 2.

Ограничения

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

1 1000000000

1

2 5

2

Задача G. Клетчатый сон ≡

Условие

Однажды крокодилу Гене приснился сон, будто он видит огромную шахматную доску, столбцы и строки которой пронумерованы числами от 0 до 30000. Как и положено, клетки доски раскрашены в чёрный и белый цвета в шахматном порядке. Левая нижняя клетка доски имеет координаты (0, 0) и окрашена в чёрный цвет.

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

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

Ограничения

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

0 0 1 1

2

3 1 5 4

6