Задача A. Две пешки и слон ≡

Условие

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

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

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

Входной файл содержит числа x₁ y₁ x₂ y₂ — координаты первой и второй пешек.

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

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

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

3 6 7 5

0

3 4 5 6

4 5

4 5 5 6

0

Задача B. Чудик в Цветландии ≡

Условие

Однажды Чудик попал в загадочную страну Цветландию. Эта страна имеет форму квадрата, разделённого на N × N маленьких квадратиков — регионов.

В каждом регионе растут цветы определённого сорта. У цветов каждого сорта есть определённый период цветения T. Цветы растут T дней, после чего увядают и начинают расти заново.

Цветы каждого региона в каждый из дней имеют определённую силу запаха, В первый день роста цветы не пахнут (сила запаха равна нулю), затем сила запаха увеличивается на единицу каждый день, вплоть до дня увядания. Таким образом, цветы с периодом цветения T в k-й день имеют силу запаха (k−1) mod T.

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

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

В k-й день путешествия Чудика в регионе с координатами (x, y) цветы имеют силу запаха (k−1) mod T(x, y), где T(x, y) — период цветения цветов этого региона.

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

Комментарий к примеру

Силы запаха в регионах по дням:

0 0
0 0

1 1
1 1

0 0
2 0

1 1
0 1

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

Входной файл содержит целые числа N K. Далее следуют N² целых чисел T(x, y).

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

Выходной файл должен содержать целое число — максимальную сумму сил запаха.

Ограничения

2 ≤ N ≤ 100

1 ≤ K ≤ 100

2 ≤ T(x, y) ≤ 100

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

2 4
2 2
3 2

4

Задача C. Крайние проекции ≡

Условие

Глеб нарисовал на координатной плоскости N точек и стал проецировать их в разных направлениях на ось ординат.

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

Глеб проецирует точки на ось ординат во всех возможных направлениях. Сначала он располагает линейку вертикально, а затем начинает разворачивать её против часовой стрелки. При этом угловой коэффициент наклона линейки возрастает от −∞ до +∞.

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

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

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

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

Далее следуют N строк, каждая из которых содержит пару вещественных чисел x_i y_i — координаты точки.

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

Выходной файл должен содержать (2 M+1) чисел, где M — количество изменений крайней точки.

Первое число — это номер точки, которая будет крайней при угловом коэффициенте наклона линейки, стремящемся к −∞. Далее идут M пар чисел k_i j_i — угловой коэффициент наклона линейки, при котором происходит изменение крайней точки, и номер точки, которая станет крайней после изменения. Пары чисел должны быть выведены в порядке возрастания углового коэффициента.

Угловой коэффициент должен быть выведен с точностью не менее 3-х знаков после запятой.

Ограничения

1 ≤ N ≤ 1000

1 ≤ x_i, y_i ≤ 100

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

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

10
5.0 3.0
6.5 2.5
9.0 2.0
3.5 4.0
1.0 3.1
7.5 1.75
2.0 2.6
6.0 3.5
10.0 1.0
9.0 1.2

9
-1.000 3
-0.500 8
-0.200 4
0.360 5

Задача D. Инкубатор Бабы Яги ≡

Условие

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

В Научно-исследовательском институте сельскохозяйственных исследований, в котором Баба Яга по совместительству работает уборщицей, заинтересовались данным феноменом. Учёные поставили задачу исследования периодичности количества ног у кур с целью дальнейшего прогнозирования этого количества.

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

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

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

Входной файл содержит целое число N, за которым следуют N целых чисел от 1 до 6 — результаты измерений количества ног у кур в течение N дней.

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

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

Если решений несколько, вывести любое из них.

Ограничения

1 ≤ N ≤ 1000

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

12
3 1 1 1 2 1 3 2 2 5 6 2

1 3 6 0 0 0

10
3 6 3 6 2 3 2 6 3 2

0 2 3 0 0 4