Задача A. Absolutely simple ≡

Условие

Вася любит уменьшать числа, но не любит отрицательных чисел. Поэтому он выбирает какое-нибудь число A₁ и начинает уменьшать его на 100, а затем брать абсолютное значение результата. Иными словами, на каждом шаге он вычисляет следующее число в последовательности A_i + 1 = |A_i − 100|.

Когда Вася вычисляет значение, уже встречавшееся в последовательности, ему становится скучно и он останавливается. Требуется написать программу, которая, получив целое число A₁, определит количество шагов, которые выполнит Вася.

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

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

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

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

Ограничения

0 ≤ |A₁| ≤ 10⁹

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

1

2

-1

4

500

6

Задача B. Breaking digits ≡

Условие

Требуется написать программу, которая, получив целое число A в десятичной записи, разделит его цифры между двумя числами B и C таким образом, чтобы:

1. Каждая цифра числа A встречалась ровно один раз либо в B, любо в C.
2. Сумма B + C была максимально возможной.

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

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

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

Выходной файл должен содержать целые числа B и C. Если существует несколько решений, выведите любое из них.

Ограничения

10 ≤ A ≤ 10⁹

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

11

1
1

439

94
3

1000

100
0

Задача C. Carriage inspectors ≡

Условие

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

В поезде N вагонов и M контролёров. На своё счастье, Вася уже давно ездит на одной и той же электричке и знает A_i — номера вагонов, где будут находиться контролёры на момент его захода в поезд. Также он знает направления движения каждого контролёра (к первому вагону или к последнему) и их скорости V_i — количество вагонов в час, которое проходит i-й контролёр. Таким образом, через каждые 1 / V_i часов контролёр переходит в следующий вагон в своём направлении. Контролёр останавливается если дальше в его направлении нет вагонов.

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

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

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

Далее следует M строк, i-я строка содержит два целых числа A_i, V_i — вагон, в котором находится соответствующий контролёр в момент захода Васи в поезд и его скорость движения. V_i отрицательна, если контролёр движется в сторону вагона с меньшим номером, и положительна в обратном случае.

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

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

Ограничения

1 ≤ N, M ≤ 200000

1 ≤ A_i ≤ N

 − 10⁶ ≤ V_i ≤ 10⁶, V_i ≠ 0

Пояснение к примерам

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

Во втором примере вагоны 1 и 5 содержат контролёров в момент времени 0. Через 0.5 часа первый контролёр заходит в вагон 4. Через 1 час от начала поездки контролёр 1 заходит в вагон 2, а контролёр 2 заходит в вагон 3. Таким образом, как 2, так и 3 является правильным ответом.

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

3 1
2 1

1

5 2
5 -2
1 1

2

Задача D. Dreaming on a train ≡

Условие

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

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

На маршруте от работы до дома Васи N станций. Каждую из них озвучивают по радио в момент, когда поезд находится на предыдущей станции. Васину станцию озвучивают на N-й станции.

Если Вася услышит название своей станции, то ни за что ее не проспит.

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

Теперь Вася думает, бороться ли ему с привычкой спать в поезде. Для этого он хочет посчитать вероятность проспать объявление своей станции.

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

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

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

В выходной файл выведите единственное число — вероятность проспать объявление своей станции с точностью не менее 5 знаков после запятой.

Ограничения

1 ≤ M ≤ N ≤ 1000

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

2 1

0.5

3 1

0.25

Задача E. Edge of the knight ≡

Условие

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

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

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

В первой строке записано расположение первого коня в формате HW, где H — обозначение колонки (вертикали), W — обозначение строки (горизонтали).

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

Выведите целое число — количество клеток, куда можно поставить второго коня.

Ограничения

H ∈ (a, b, c, d, e, f, g, h)

1 ≤ W ≤ 8

Пояснение к примерам

Напомним, что фигура конь ходит буквой Г. То есть во время своего хода конь перемещается в одном из направлений (вертикальном или горизонтальном) на 1 одну клетку, а в другом направлении — на 2 клетки.

В первом примере второго коня можно поставить в клетки c1, g1, c3, g3, d4 и f4.

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

e2

6

f5

8

Задача F. 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

Задача G. Gablerd Lettres ≡

Условие

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

Алексей решил проверить, будет ли выполняться это свойство для целых чисел. Он придумал число N и хочет переставить в нём цифры так, чтобы:

• первая и последняя цифры остались на своих местах;
• все остальные цифры изменили своё положение.

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

Напишите программу которая переставляет цифры данного числа в соответствии с требованиями Алексея.

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

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

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

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

Если ответа не существует, выведите  − 1.

Ограничения

1 ≤ N ≤ 10⁹

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

238965

269385

123

-1

Задача H. Healthy run ≡

Условие

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

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

Бегать нужно по круговой дорожке, разбитой на N отрезков. Длина i-го отрезка составляет a_i метров.

Отрезки следует пробегать, чередуя медленный и быстрый бег: первый, третий и последующие нечётные отрезки — со скоростью V м/с, второй, четвёртый и последующие чётные отрезки — со скоростью 2V м/с.

Для заданного набора отрезков круговой дорожки и стартовой скорости Васе стало интересно, сколько метров он пробежит за T секунд.

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

Первая строка входного файла содержит целые числа N, V, T — количество отрезков, начальная скорость и время, которое пробежит Вася.

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

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

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

Ограничения

1 ≤ N ≤ 10⁴

1 ≤ a_i ≤ 10⁴

1 ≤ V, T ≤ 10⁴

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

1 2 1
1

2.5

2 10 2
3 7

30.5

Задача I. Inverse breaking digits ≡

Условие

Требуется написать программу, которая, получив целое число A в десятичной записи, разобьёт его на два числа B и C таким образом, чтобы:

1. Каждая цифра числа A встречалась ровно один раз либо в B, любо в C.
2. Сумма B + C была минимально возможной.
3. Числа B и C не содержали лидирующих нулей.

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

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

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

Выходной файл должен содержать целые числа B и C. Если существует несколько решений, выведите любое из них.

Ограничения

10 ≤ A ≤ 10¹⁸

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

11

1
1

439

34
9

1000

100
0