Задача A. Результаты квалификации ≡

Условие

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

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

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

Когда гонщик завершает очередной круг, в журнал записываются числа B_i и T_i — номер его машины и разность между временем, за которое он проехал этот круг, и текущим лучшим среди всех гонщиков временем. (T_i измеряется в тысячных долях секунды, T₁ всегда равно 0). Если T_i < 0, то время, показанное этим гонщиком, становится лучшим.

Требуется определить результат квалификации по записям в журнале.

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

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

Далее содержатся N пар целых чисел B_i T_i — записи в журнале в хронологическом порядке.

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

Выходной файл должен содержать номера гоночных автомобилей, перечисленные в порядке расположения на старте гонки.

Ограничения

1 ≤ N ≤ 10⁵

Разница между лучшим и худшим временем не превышает 10⁹ тысячных секунды

1 ≤ B_i ≤ 10⁶

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

6
7
+0
2
+123
5
-11
2
+7
1
+0
3
+60200

5 1 2 7 3

Задача B. Развлечение с калькулятором ≡

Условие

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

Сначала они выбирают какую-нибудь цифру D и нажимают соответствующую ей клавишу на калькуляторе N раз подряд. Затем они:

1. Проверяют, что число на экране делится на два и не равно нулю. Если это не так, развлечение прекращается.
2. Делят текущее число на два, вычитают из результата единицу и снова переходят к шагу 1.

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

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

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

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

Выходной файл должен содержать получившееся число, записанное без лидирующих нулей.

Ограничения

1 ≤ D ≤ 9, 1 ≤ N ≤ 10⁵

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

1 1

1

2 3

5

Задача C. Футбольный чемпионат ≡

Условие

В футбольном чемпионате приняли участие N команд. Каждая команда провела N − 1 игру на своем поле и столько же выездных игр (т.е. всего произошло N(N − 1) встреч). Каждая игра оканчивается либо победой одной из команд, либо ничьей. В случае ничьей обе команды получают по одному очку, в противном случае команда-победитель получает три очка, проигравшая команда — ноль.

Турнирная таблица представляет собой таблицу чисел N × N. По диагонали таблицы стоят нули. При i ≠ j, j-ый элемент на i-ой строке равен количеству очков, которое i-ая команда заработала в матче с j-ой командой на своем поле.

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

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

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

Ограничения

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

2
1 4

0 1
3 0

2
5 5

0 0
0 0

Задача D. Скорость воробьёв ≡

Условие

Юный орнитолог Вася решил узнать, насколько быстро способны летать воробьи. Для этого он нашёл ряд из N кустов, растущих вдоль одно прямой на расстоянии ровно 1 метр друг от друга.

Воробьи часто сидят на кустах и перелетают с одного на другой. Вася сделал две фотографии деревьев с воробьями с интервалом ровно в 1 секунду. К сожалению, все воробьи выглядят одинаково, и Вася не может по фотографии определить, какой воробей куда перелетел.

Однако оказалось, что на первой фотографии на каждом из кустов сидит ровно по одному воробью, а на второй — на i-м кусте сидят a_i воробьёв. (a₁ + a₂ + … + a_N = N).

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

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

Во входном файле содержится число N, за которым следует N целых чисел a_i.

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

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

Ограничения

1 ≤ N ≤ 1000

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

3
1 1 1

0

5
0 2 3 0 0

2

Задача E. Соединительная линия ≡

Условие

На плоскости, разделённой на клетки, заданы два прямоугольника с координатами (x₁, y₁)−(u₁, v₁), (x₂, y₂)−(u₂, v₂) и две различные точки с координатами (x_s, y_s) и (x_d, y_d). Требуется:

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

При этом пустая клетка должна изображаться символом '.', клетка, принадлежащая прямоугольнику — символом '#', начальная и конечная точки — символом '*', клетка, через которую путь проходит по горизонтали — символом '-', клетка, через которую путь проходит по вертикали — символом '|', клетка, в которой путь делает поворот — символом '+'.

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

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

Во входном файле содержатся целые числа x₁ y₁ u₁ v₁ x₂ y₂ u₂ v₂ x_s y_s x_d y_d.

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

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

Ограничения

1 ≤ x_i, y_i, u_i, v_i ≤ 100,

Прямоугольники могут пересекаться. Начальная и конечная точки не лежат внутри прямоугольников.

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

2 3 7 5  6 7 8 8  6 2  5 9

...*...
...|###
...|###
...+--+
######|
######|
######|
....*-+

2 3 7 6  8 7 6 8  6 2  5 9

...*---+
....###|
....###|
######++
######|.
######|.
######|.
....*-+.

Задача F. Самый острый угол ≡

Условие

В данном множестве из N точек на плоскости с координатами (x_i, y_i) требуется найти такие три точки A, B и C, что ∠ ABC будет наименьшим.

Никакие три точки в исходном множестве не лежат на одной прямой.

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

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

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

В выходном файле должно содержаться три целых числа A B C — номера вершин минимального угла. Точки нумеруются с 1. Если решений несколько, выведите любое из них.

Ограничения

3 ≤ N ≤ 10³

0 ≤ x_i, y_i ≤ 10⁶

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

3
5 5  5 4  10 4

1 3 2

Задача G. Однокоренные слова ≡

Условие

Слова марсианского языка записываются малыми латинскими буквами. При этом буквы a, e, i, o, u, y считаются гласными, а остальные — согласными.

Марсианские слова состоят из необязательной приставки, корня, и необязательного суффикса. При этом все приставки заканчиваются на согласную букву, а все суффиксы — начинаются с согласной буквы.

Например, слово marsianin может быть записано в виде приставка(корень)суффикс как: m(arsianin), mar(sia)nin, (mar)sianin, и другими способами.

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

Требуется по данным двум марсианским словам определить, являются ли они однокоренными.

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

В первой строке входного файла содержится первое слово, во второй — второе слово.

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

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

Ограничения

Слова имеют длину от 1 до 100 символов.

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

aceei
cee

NO

aceeidceef
cee

YES

y
y

YES