Задача A. Absolutely simple

Автор:A. Klenin   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

0 ≤ |A1| ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1
2
2
-1
4
3
500
6

Задача B. Breaking digits

Автор:A. Klenin   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

10 ≤ A ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
11
1
1
2
439
94
3
3
1000
100
0

Задача C. Carriage inspectors

Автор:M. Sporyshev, I. Tuphanov   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N, M ≤ 200000

1 ≤ Ai ≤ N

 − 106 ≤ Vi ≤ 106, Vi ≠ 0

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

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

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 1
2 1
1
2
5 2
5 -2
1 1
2

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

Автор:M. Sporyshev   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ M ≤ N ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 1
0.5
2
3 1
0.25

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

Автор:A. Usmanov   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

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

1 ≤ W ≤ 8

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

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

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
e2
6
2
f5
8

Задача F. Flasks equalizing

Автор:M. Sporyshev, A. Zhikhareva   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 105

0 ≤ ai ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5
7 7 1 5 5
2
2 0 4
1 0 2
2
5
7 6 1 5 6
4
2 0 3
4 1 0
1 0 2
5 1 0

Задача G. Gablerd Lettres

Автор:A. Usmanov   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
238965
269385
2
123
-1

Задача H. Healthy run

Автор:M. Sporyshev   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 104

1 ≤ ai ≤ 104

1 ≤ V, T ≤ 104

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 2 1
1
2.5
2
2 10 2
3 7
30.5

Задача I. Inverse breaking digits

Автор:A. Klenin   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

10 ≤ A ≤ 1018

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

Входной файл (input.txt) Выходной файл (output.txt)
1
11
1
1
2
439
34
9
3
1000
100
0

0.687s 0.017s 29