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

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

Условие

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

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

Входные данные содержат четыре целых числа — x0,y0,x1,y1.

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

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

Ограничения

|x0|,|y0|,|x1|,|y1| ≤ 105

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

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

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

Автор:М. Спорышев   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ A, L, R ≤ 109

1 ≤ X, Y ≤ 108

L < R

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

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
A, L, RX,Y
1451 ≤ A, L, R ≤ 1061 ≤ X, Y ≤ 1000полная
2551 ≤ A, L, R ≤ 1091 ≤ X, Y ≤ 108полная

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

Стандартный вход Стандартный выход
1
1 3 2 1 1
3
2
7 10 11 2 3
16

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

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

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 105

1 ≤ xi, hi ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5
1 2
2 1
3 3
7 5
8 2
3
2
3
6 10
7 1
15 2
3
3
4
10 20
31 9
50 1
55 5
1

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

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

Условие

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 106; 1 ≤ K ≤ 105; 1 ≤ ai ≤ N

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

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

Подзадача Баллы Дополнительные ограничения
NK
1151 ≤ N ≤ 105, N - чётноеK = N / 2
2351 ≤ N ≤ 201 ≤ K ≤ 10
3501 ≤ N ≤ 1061 ≤ K ≤ 105

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

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

0.522s 0.036s 19