Задача A. Аквалангист ≡

Условие

Аквалангист Джонс находится в море в координате x_j, y_j на глубине h_j метров. Джонс заметил акулу, которая находится в координате x_s, y_s на глубине h_s метров. Акула тоже заметила Джонса.

Успеет ли Джонс выплыть вертикально вверх к поверхности со скоростью 1 м/с раньше, чем акула достигнет Джонса, если акула способна двигаться только параллельно осям координат со скоростью v_s м/с и приближается к нему по одному из кратчайших путей?

Если Джонс достиг поверхности одновременно с тем, как акула достигла Джонса, считается, что он не успел.

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

Входные данные содержат в двух строках целые числа x_j, y_j, h_j и x_s, y_s, h_s, v_s.

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

Выходные данные должны содержать YES, если Джонс успеет выплыть и NO в ином случае.

Ограничения

0 ≤ |x_j|, |y_j|, h_j, |x_s|, |y_s|, h_s ≤ 10⁵

1 ≤ v_s ≤ 100

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

0 0 1
100 100 100 1

YES

0 0 1
0 0 2 2

NO

Задача B. Быки и коровы 2 ≡

Условие

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

На поле периодически нападают волки, поэтому пастухи решили оградить участок длиной h клеток.

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

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

В первой строке входного файла заданы числа N, h. Далее идёт строка из N символов, где каждый символ — либо '.' (ASCII 46), что означает пустую клетку, либо 'X' (ASCII 88), обозначающий корову, либо 'Y' (ASCII 89), обозначающий быка.

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

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

Ограничения

1 ≤ N < 10⁵, 1 ≤ h ≤ N

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

15 5
XX...XXYYYXX.YY

6 10

Задача C. Жадная последовательность ≡

Условие

Дана последовательность из N целых чисел a_i. Над последовательностью M раз выполняется следующая операция. Из последовательности удаляются два наименьших числа и добавляется в конец число равное сумме двух удаленных. Если наименьших чисел более двух, следует выбрать числа с наименьшими номерами в последовательности.

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

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

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

Вторая строка входного файла содержит N целых чисел a_i — элементы последовательности.

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

В выходной файл требуется вывести элементы последовательности после M выполнений вышеописанной операции.

Ограничения

1 ≤ M < N ≤ 10⁵

−10⁴ ≤ a_i ≤ 10⁴

Описание подзадач и системы оценивания

Баллы за подзадачи 1,2 начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены. Баллы за подзадачу 3 начисляются за каждый пройденный тест, если тесты необходимых подзадач пройдены.

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

4 1
1 2 3 4

3 4 3

4 2
3 2 1 1

3 4

Задача D. Сбор справок ≡

Условие

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

Будем считать, что чиновники занумерованы целыми числами от 1 до N. Тот факт, что для посещения чиновника с некоторым номером, требуется справка от чиновника с другим номером, будем называть "условием".

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

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

Ограничения

Описание подзадач и системы оценивания

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

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

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

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

4 3
1 2
1 3
3 4

YES

4 3
1 2
2 3
3 1

NO

Задача E. Flasks equalizing ≡

Условие

В лаборатории стоит необычная конструкция из N одинаковых цилиндрических сосудов, выстроенных в ряд.

В i-й сосуд налито a_i миллилитров жидкости.

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

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

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

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

Вторая строка содержит N целых чисел a_i. Гарантируется, что общее количество жидкости делится на N.

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

Первая строка выходного файла должна содержать целое число S — минимальное число шагов.

Следующие S строк содержат по три целых числа I, L, R — индекс сосуда, начиная с 1, увеличение уровня в соседнем слева сосуде, увеличение уровня в соседнем справа сосуде соответственно.

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

Ограничения

1 ≤ N ≤ 10⁵

0 ≤ a_i ≤ 10⁹

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

5
7 7 1 5 5

2
2 0 4
1 0 2

5
7 6 1 5 6

4
2 0 3
4 1 0
1 0 2
5 1 0