Задача A. Медоед и двери ≡

Условие

Юный Медоед Афанасий живет в одномерном доме. В его доме есть две двери, которые автоматически открываются и закрываются и находятся в координатах L и R (L < R). Однажды, находясь в координате 0, медоед Афанасий увидел змею, которая находилась в координате A. Афанасий не любит посторонних и решает прогнать змею, для чего он начинает двигаться со скоростью 1 метр в секунду в сторону змеи. Змея стоит неподвижно.

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

Если медоед попадает в координату с дверью, которая закрылась в этот момент времени, то ждет, когда дверь откроется. Аналогично, если медоед попадает в координату с дверью, которая в этот момент открылась, он идет дальше.

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

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

Первая строка входного файла содержит целые числа L, R, A, X, Y.

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

Выходные данные должны содержать единственное целое число — ответ на задачу.

Ограничения

1 ≤ A, L, R ≤ 10⁹

1 ≤ X, Y ≤ 10⁸

L < R

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

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

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

1 3 2 1 1

3

7 10 11 2 3

16

Задача B. Криптоаналитика за еду ≡

Условие

Начинающий программист Коля заинтересовался криптографией. Изучая различные алгоритмы шифрования, ему захотелось придумать свой собственный. Недолго подумав, он нарисовал табличку, которая выглядит следующим образом:

На основании неё он построил следующий алгоритм: в каждом слове последовательно выбирается буква W₁ и соответствующая ей строка таблицы, затем берется следующая за ней буква W₂ и соответствующий ей столбец, и после этого W₁ шифруется символом, находящимся на пересечении выбранных строки и столбца. Так продолжается до последней буквы, которая шифруется с помощью первой буквы уже зашифрованного слова. К примеру, строка "HELLO" после шифрования запишется как "LPWZZ".

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

Помогите Никите узнать, что же за текст скрывается в этом странном сообщении.

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

Первая строка входного файла содержит строку S — зашифрованное сообщение. Длина строки не превосходит 10⁵ и состоит только из заглавных букв латинского алфавита A-Z (ASCII 65-90).

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

Выходной файл должен содержать строку с расшифрованным сообщением.

Ограничения

2 ≤ N ≤ 10⁵, где N — длина строки.

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

LPWZZ

HELLO

Задача C. Домино ≡

Условие

Утконос Джордж очень любит домино. У него имеется N доминошек, которые он располагает вертикально вдоль координатной прямой. i —ая доминошка имеет координату x_i и высоту h_i. Все координаты x_i строго возрастают. Бобер Саймон завидует Джорджу и понимает, что Джордж сильно расстроится, когда увидит, что какие-то его доминошки упали. Саймон может толкнуть ровно одну доминошку так, что она начнет падать в положительном направлении координатной прямой. При падении возникает цепная реакция: доминошка i толкнет доминошку i + k, если разница их координат не превосходит высоты i —ой доминошки.

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

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

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

Следующие N строк содержат по два числа x_i, h_i

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

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

Ограничения

1 ≤ N ≤ 10⁵

1 ≤ x_i, h_i ≤ 10⁹

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

5
1 2
2 1
3 3
7 5
8 2

3

3
6 10
7 1
15 2

3

4
10 20
31 9
50 1
55 5

1

Задача D. Рассадка пассажиров ≡

Условие

Илон Маск закончил создание транспорта будущего — Hyperloop. Hyperloop — расположенный на опорах надземный трубопровод, внутри которого с высокой скоростью в одном направлении перемещаются одиночные транспортные капсулы. Пассажирский вариант предполагает n рядов по одному сиденью. Однако из-за конструктивных недостатков люди не могут сидеть на двух подряд идущих рядах. Поэтому, когда продаётся билет с номером места a_i из продажи исчезает сам этот билет, и два соседних с ним билета.

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

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

Первая строка входного файла содержит два целых числа N и K. Далее следует K строк содержащих по одному числу a_i. Гарантируется, что для всех пар i и j выполняется условие |a_i − a_j| ≥ 2 .

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

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

Ограничения

1 ≤ N ≤ 10⁶; 1 ≤ K ≤ 10⁵; 1 ≤ a_i ≤ N

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

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

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

4 2
2
4

1

3 0

2

5 1
1

2

Задача E. Заморозки в Невеции ≡

Условие

Точки города Невеция связаны водными каналами, i-й из которых имеет ширину w_i. Каналы спроектированы так, что из любой точки города можно на лодке попасть в любую другую. Лодка может проплыть по каналу, если её ширина не превосходит ширины канала.

В Невеции ударили морозы, и скоро водные каналы станут ледяными. Физики Невеции обнаружили, что каналы замерзают на один метр в сутки по ширине с каждой стороны, становясь таким образом с каждым днем всё ́́уже.

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

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

Входные данные содержат целые числа N, M и W — количество точек города, количество каналов и ширина лодок. Далее следуют M троек целых чисел a_i b_i w_i — точки, которые соединяет канал, и его ширина. Каждый канал описывается ровно один раз.

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

Выходные данные должны содержать одно целое число.

Ограничения

2 ≤ N ≤ 10³

1 ≤ a_i, b_i ≤ N

1 ≤ M ≤ N(N−1)2

1 ≤ w_i, W ≤ 10⁹

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

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

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

4 3 5
1 2 15
2 3 11
3 4 20

4

2 1 1
1 2 3

2

3 3 10
1 2 9
1 3 10
2 3 10

1