Задача A. По клеткам ≡

Условие

Робот находится в клетке с координатой (x₀, y₀) и направлен в сторону возрастания y. Ему необходимо попасть в клетку (x₁, y₁). При этом робот за ход может либо сделать шаг вперед на одну клетку, либо повернуться влево на 90° и сделать шаг вперед. Необходимо посчитать, какое минимальное количество ходов должен потратить робот, чтобы добраться из точки (x₀, y₀) в (x₁, y₁).

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

Входные данные содержат четыре целых числа — x₀,y₀,x₁,y₁.

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

Выходные данные должны содержать одно целое число — количество ходов, которые должен потратить робот.

Ограничения

|x₀|,|y₀|,|x₁|,|y₁| ≤ 10⁵

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

1 1 -3 5

8

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

Условие

Юный Медоед Афанасий живет в одномерном доме. В его доме есть две двери, которые автоматически открываются и закрываются и находятся в координатах 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

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