Задача A. Тройной захват ≡

Условие

Дано множество из N различных точек на плоскости и точка A. Требуется выбрать из множества три такие точки, что:

1. существует треугольник с вершинами в этих точках,
2. точка A лежит внутри треугольника или на его границе.

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

Входной файл содержит целое число N, за которым следуют целые числа x_A y_A — координаты точки A.

Далее следует N пар чисел x_i y_i — координаты точек множества.

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

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

Гарантируется, что точки, удовлетворяющие условию задачи, существуют.

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

Ограничения

3 ≤ N ≤ 100000.

−10000 ≤ x_A, y_A, x_i, y_i ≤ 10000

Разбалловка

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

6
2 0
1 0
3 4
3 2
1 -2
0 0
3 0

6 1 2

Задача B. Хоттаб-share/2 ≡

Условие

Прожив 1000 лет, Гассан Абдуррахман ибн Хоттаб узнал, что из интернета можно скачивать файлы. Решив помочь другим пользователям, он сотворил собственный сервер с файлами. Поскольку сервер Хоттаба волшебный, любой файл скачивается с него мгновенно. Однако, после скачивания файла размером S мегабайт скачавший его компьютер отключается от сервера на S секунд.

В распоряжении шушанчиков имеется один компьютер, подключённый к интернету. Им требуется скачать N файлов, i-й файл размером s_i мегабайт. Шушанчики просят Вас рассчитать минимальное время, за которое можно скачать эти файлы с сервера Хоттабыча.

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

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

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

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

Ограничения

1 ≤ N ≤ 1000

1 ≤ s_i ≤ 1000

Все числа во входном файле целые

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

2
13 17

13

5
13 19 17 14 19

63

Задача C. Сумма 0, произведение N ≡

Условие

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

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

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

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

Требуется вывести N чисел — ответ в задаче. Числа выводить в произвольном порядке.

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

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

Ограничения

4 ≤ N ≤ 1000.

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

4

2 1 -1 -2

Задача D. Сколько прошло дней? ≡

Условие

Был день d.m.y₁.

Прошло ровно N лет, и наступил день d.m.y₂, где y₂ = y₁ + N.

Здесь d — число месяца, m — месяц, y_i — год. Обратите внимание, что в датах d.m.y₁ и d.m.y₂ дни и месяцы соответственно равны, даты отличаются только годами.

Сколько прошло дней?

Примечание. В обычном году 365 дней, в високосном — 366. В феврале обычного года 28 дней, в феврале високосного 29 дней. Год Y високосный, если Y делится на 4, но не делится на 100. Если Y делится на 100, но не делится на 400, то год не високосный. Если Y делится на 400, то год високосный.

Например, 2009 год не високосный (2009 не делится на 4), 2008 — високосный (2008 делится на 4), 2000 — високосный (2000 делится на 400), 1900 — не високосный (1900 делится на 100, но не делится на 400).

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

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

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

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

Ограничения

1 ≤ N ≤ 100000

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

1

365 366

Задача E. Сладкая симметрия ≡

Условие

У Алисы и Боба была коробка конфет. Коробка имеет прямоугольную форму и разбита на N × M квадратных ячеек (N по вертикали и M по горизонтали). В каждой ячейке изначально находилась конфета.

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

В первой строке входного файла содержатся числа N M. В последующих N строках содержится по M символов '.' или '#'. Точка обозначает пустую ячейку, решетка — ячейку, занятую конфетой.

На картинке приведен пример перекладывания конфеты для первого теста и обозначена ось симметрии.

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

В выходной файл выведите единственное число — минимальное необходимое количество перекладываний, либо −1, если уложить конфеты симметричным образом невозможно.

Ограничения

1 ≤ N, M ≤ 50;

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

4 5
.....
.....
.....
#....

1

4 4
....
..#.
....
#..#

-1

5 4
....
.#..
....
#...
..##

2