Информатика

Два друга-биолога Василий и Петр едут в Африку на поезде. Билеты они покупали в разное время и не смогли получить места в одном вагоне. Василий купил билет на место с номером X, а Петр — на место с номером Y .
Все поезда в структуре РЖД комплектуются вагонами с одинаковым числом посадочных мест, равным K. Нумерация мест сквозная: в первом вагоне расположены места с номерами от 1 до K, во втором вагоне — места с номерами от K + 1 до 2K, и так далее. Помогите Василию посчитать,сколько раз он должен перейти из одного вагона в соседний для встречи с Петром.

Входные данные
В первой строке входных данных записано целое число K (1 ≤ K ≤ 10⁹) — число посадочных мест в каждом вагоне.
Во второй строке записано целое число X — номер места Василия.
В третьей строке записано целое число Y (1 ≤ X < Y ≤ 10⁹) — номер места Петра.

Выходные данные
Выведите одно целое число — количество переходов Василия из одного вагона в соседний.
 

Примеры

№	Входные данные	Выходные данные
1	3 3 7	2

Горилла Коко очень любит путешествовать по своим родным джунглям с помощью лиан.
Всего в джунглях есть N лиан, расположенных друг за другом и пронумерованных слева направо целыми числами от 1 до N. Расстояние между соседними лианами составляет D метров. Находясь на i-й лиане, Коко может совершить прыжок с нее не более, чем на ai метров вправо. В процессе прыжка Коко должна зацепиться за какую-то другую лиану, мимо которой будет пролетать.
В данный момент Коко висит на первой лиане и хочет переместиться как можно дальше вправо.
Помогите Коко и определите максимальный номер лианы, до которой она сможет добраться.

Входные данные
Первая стока входных данных содержит целое число N (2 ≤ N ≤ 10⁵) — количество лиан.
Во второй строке записано целое число D (1 ≤ D ≤ 10⁹) — расстояние между соседними лианами.
В каждой из следующих N строк записано целое число ai (1 ≤ a_i ≤ 10⁹) — на сколько метров вправо может прыгнуть Коко, находясь на i-й лиане.

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

Примеры

№	Входные данные	Выходные данные
1	5 3 7 8 2 2 6	4

Замечание
В примере из условия дано 5 лиан, а расстояние между лианами равно 3 метрам. Находясь на первой лиане, Коко может прыгнуть не более, чем на 7 метров, то есть она сможет допрыгнуть до второй и третьей лианы. Ей нужно остановиться на второй лиане, потому что со второй лианы длина прыжка равна 8 метрам, и это позволит ей допрыгнуть до четвёртой лианы. С четвёртой лианы длина прыжка равна 2 и это меньше, чем расстояние до следующей лианы, поэтому Коко остановится на четвёртой лиане.

Андрей вот-вот опоздает на школьный этап ВсОШ. К счастью, недавно в его городе появились порталы.
Город, в котором живет Андрей, можно представить в виде прямой. Всего в городе успели построить N порталов. Портал с номером i расположен в точке с координатой x_i . Если в текущий момент времени вы находитесь в одной точке с каким-нибудь порталом, то можете всего за одну секунду телепортироваться в любой другой портал вне зависимости от расстояния между ними. А время, требуемое для преодоления расстояния между точками с координатами p и q без использования порталов равно |p − q| секунд. Андрей является влиятельным гражданином, поэтому он может использовать систему порталов любое количество раз.
Изначально Андрей находится в точке s, а точка проведения олимпиады имеет координату e.
Помогите Андрею понять, как быстро он может попасть на олимпиаду, ведь каждая секунда на счету.

Входные данные
В первой строке входных данных записано одно целое число s — начальное положение Андрея.
Во второй строке записано одно целое число e — место проведения олимпиады. 
В третьей строке записано количество порталов N (2 ≤ N ≤ 2 · 10⁵).
В каждой из N следующих строк записано целое число x_i — координата портала с номером i.
Все числа s, e, x_i по модулю не превосходят 10⁸.

Выходные данные
Выведите одно число — минимальное количество секунд, которое потребуется Андрею для того, чтобы добраться до места проведения олимпиады.
 
Примеры

№	Входные данные	Выходные данные
1	0 4 3 1 3 5	3

Замечание
Рассмотрим пример из условия. Если бы Андрей не мог пользоваться порталами, он бы смог добраться до точки проведения олимпиады за |0 − 4| = 4 секунды. Однако, можно действовать так:
1. Дойти до портала с номером 1 за |0 − 1| = 1 секунду.
2. Телепортироваться в портал с номером 2 за одну секунду.
3. Дойти от портала с номером 2 до точки проведения олимпиады за |3 − 4| = 1 секунду.
Суммарно получаем 1 + 1 + 1 = 3 секунды.

Персонаж известной компьютерной игры Марио постарел и почти перестал прыгать. Но совсем недавно он увидел спуск из N ступенек, и его накрыло ностальгией. Марио встал на самую верхнюю ступеньку и решил преодолеть этот спуск при помощи прыжков.
Когда-то Марио знал тысячи различных видов прыжков, но теперь он смог вспомнить только два: короткие и длинные. Короткий прыжок позволяет спуститься на произвольное число ступенек, не большее X, а длинный — на произвольное число, не большее Y (X < Y ). Но в силу возраста Марио не может делать два длинных прыжка подряд и вынужден между ними совершать хотя бы один короткий. При этом Марио не хочет слишком уж сильно ухудшить свои прошлые результаты и поэтому постарается обойтись как можно меньшим числом прыжков.
Помогите Марио посчитать минимальное количество прыжков, требующееся для преодоления всех N ступенек.

Входные данные
В первой строке входных данных записано целое число X — максимальная длина короткого прыжка.
Во второй строке записано целое число Y (1 ≤ X < Y ≤ 10¹⁸) — максимальная длина длинного прыжка.
В третьей строке записано целое число N (1 ≤ N ≤ 10¹⁸) — количество ступенек в спуске.

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

Примеры

№	Входные данные	Выходные данные
1	2 3 5	2
2	1 2 4	3
3	1 100 1000000000000000000	19801980198019801

Замечание
На изображениях ниже приведены возможные способы решения первых двух тестов из условия:

Коротышки решили взять в полет на Луну либо Незнайку либо Пончика. Не сумев договориться, они решили проголосовать. Незнайка и Пончик наблюдают краткий отчет о голосовании. Коротышки показывают Незнайке и Пончику соотношение текущего количества голосов, полученных Незнайкой и Пончиком, но не фактическое количество голосов. Незнайка и Пончик посмотрели отчет N раз, и когда они смотрели его в i-й (1<=i<=N) раз, соотношение было Pi:Ni. Известно, что Незнайка и Пончик имели хотя бы один голос, когда впервые увидели отчет. Найдите минимально возможное общее количество голосов, полученных Незнайкой и Пончиком, когда они проверили отчет в N-й раз. Можно предположить, что количество голосов, полученных Незнайкой и Пончиком, никогда не уменьшается.

Входные данные
В первой строке задается целое число N (1<=N<=1000). В следующих N строках записано по 2 числа Pi и Ni (1<=P_i,N_i<=1000). Pi и Ni - взаимно простые числа. 

Выходные данные
Выведите минимально возможное общее количество голосов. Гарантируется, что правильный ответ - не более 10¹⁸.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 2 3 1 1 3 2	10	Количество голосов, полученных Пончиком и Незнайкой, изменяется так 2,3 → 3,3 → 6,4. Общее количество голосов в конце составляет 10, что является минимально возможным числом.
2	4 1 1 1 1 1 5 1 100	101	Возможно, что ни Пончик ни Незнайка не получили голосов между моментом, когда они смотрели отчет, и моментом, когда они смотрели его в следующий раз.
3	5 3 10 48 17 31 199 231 23 3 2	6930

Подсчитайте количество натуральных делителей числа x (включая 1 и само число x).

Входные данные
Вводится натуральное число x (x < 30000).

Выходные данные
Выведите единственное число - количество делителей числа x.
 

Примеры

№	Входные данные	Выходные данные
1	32	6

Найдите самый маленький натуральный делитель числа x, отличный от 1 (2 <= x <= 30000).

Входные данные
Вводится натуральное число x.

Выходные данные
Выведите наименьший делитель числа x, отличный от 1.

Примеры

№	Входные данные	Выходные данные
1	6	2

Юра Баранкин заполнял таблицу истинности функции \(((z \rightarrow w) \rightarrow (\bar y \wedge x)) \equiv (w \rightarrow x)\). В тот момент когда его позвал гулять Костя, Юра успел заполнить лишь фрагмент из трёх различных строк таблицы. После прогулки Юра заметил, что не указал, к какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

?	?	?	?	F
	0	1		0
1		0	0	0
1	0		0	0

Помогите Юре восстановить столбцы таблицы. Укажите какому столбцу соответствует каждая из переменных w, x, y, z. 
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Юра Баранкин заполнял таблицу истинности функции \((y \rightarrow \neg(z \vee w)) \vee (x \wedge (w \rightarrow z))\). В тот момент когда его позвал гулять Костя, Юра успел заполнить лишь фрагмент из трёх различных строк таблицы. После прогулки Юра заметил, что не указал, к какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

?	?	?	?	F
1			0	0
0		1		0
		1		0
1		0	1	0

Помогите Юре восстановить столбцы таблицы. Укажите какому столбцу соответствует каждая из переменных w, x, y, z. 
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Юра Баранкин заполнял таблицу истинности функции \((\bar x \equiv y) \rightarrow ((z \wedge \bar w) \neq (w \wedge \bar y))\). В тот момент когда его позвал гулять Костя, Юра успел заполнить лишь фрагмент из трёх различных строк таблицы. После прогулки Юра заметил, что не указал, к какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

?	?	?	?	F
1		1	0	0
1				0
1	1	1		0

Помогите Юре восстановить столбцы таблицы. Укажите какому столбцу соответствует каждая из переменных w, x, y, z. 
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

На рисунке изображена схема дорог некоторого района области в виде графа, в таблице указана длина этих дорог в километрах. Таблицу и схему рисовали независимо друг от друга, нумерация деревень в таблице никак не связана с буквенными обозначениями на графе. Определите длину более длинной дороги из дорог АЖ и ВЗ. В ответе запишите целое число – так, как оно указано в таблице.
 

На рисунке изображена схема дорог некоторого района области в виде графа, в таблице указана длина этих дорог в километрах. Таблицу и схему рисовали независимо друг от друга, нумерация деревень в таблице никак не связана с буквенными обозначениями на графе. Определите длину более короткой дороги из дорог АЖ и ВЗ. В ответе запишите целое число – так, как оно указано в таблице.
 

На рисунке изображена схема дорог некоторого района области в виде графа, в таблице указана длина этих дорог в километрах. Таблицу и схему рисовали независимо друг от друга, нумерация деревень в таблице никак не связана с буквенными обозначениями на графе. Определите длину более длинной дороги из дорог ДЖ и ДЗ. В ответе запишите целое число – так, как оно указано в таблице.
 

На рисунке изображена схема дорог некоторого района области в виде графа, в таблице указана длина этих дорог в километрах. Таблицу и схему рисовали независимо друг от друга, нумерация деревень в таблице никак не связана с буквенными обозначениями на графе. Определите длину более короткой дороги из дорог ДЖ и ДЗ. В ответе запишите целое число – так, как оно указано в таблице.
 

На рисунке изображена схема дорог некоторого района области в виде графа, в таблице указана длина этих дорог в километрах. Таблицу и схему рисовали независимо друг от друга, нумерация деревень в таблице никак не связана с буквенными обозначениями на графе. Определите длину более длинной дороги из дорог ДЕ и ДЖ. В ответе запишите целое число – так, как оно указано в таблице.
 

На рисунке изображена схема дорог некоторого района области в виде графа, в таблице указана длина этих дорог в километрах. Таблицу и схему рисовали независимо друг от друга, нумерация деревень в таблице никак не связана с буквенными обозначениями на графе. Определите длину более короткой дороги из дорог ДЕ и ДЖ. В ответе запишите целое число – так, как оно указано в таблице.
 

На рисунке изображена схема дорог некоторого района области в виде графа, в таблице указана длина этих дорог в километрах. Таблицу и схему рисовали независимо друг от друга, нумерация деревень в таблице никак не связана с буквенными обозначениями на графе. Определите длину более короткой дороги из дорог ЕЗ и ЖЗ. В ответе запишите целое число – так, как оно указано в таблице.
 

Выведите фамилии и имена учащихся в порядке убывания их среднего балла.

Входные данные
Заданы сначала количество учащихся n, затем n строк, каждая из которых содержит фамилию, имя и три числа (оценки по трем предметам: математике, физике, информатике). Данные в строке разделены одним пробелом. Оценки принимают значение от 1 до 5.

Общее число учащихся не превосходит 100001.
Выходные данные
Необходимо вывести пары фамилия-имя по одной на строке, разделяя фамилию и имя одним пробелом. Выводить оценки не нужно. Если несколько учащихся имеют одинаковые средние баллы, то их нужно выводить в порядке, заданном во входных данных.
 

Примеры

№	Входные данные	Выходные данные
1	2 Markov Valeriy 1 1 1 Ivanov Ivan 2 2 2	Ivanov Ivan Markov Valeriy
2	3 Markov Valeriy 5 5 5 Sergey Petrov 1 1 1 Petrov Petr 3 3 3	Markov Valeriy Petrov Petr Sergey Petrov

На рисунке изображена схема дорог некоторого района области в виде графа, в таблице указана длина этих дорог в километрах. Таблицу и схему рисовали независимо друг от друга, нумерация деревень в таблице никак не связана с буквенными обозначениями на графе. Определите длину более длинной дороги из дорог ЕЗ и ЖЗ. В ответе запишите целое число – так, как оно указано в таблице.
 

Определите трех учащихся с наилучшим средним баллом по трем предметам. Выведите фамилии и имена этих учащихся. Если при этом у нескольких учащихся средний балл совпадает со средним баллом учащегося, "занявшего 3-е место", то необходимо вывести их всех.

Входные данные
Заданы сначала количество учащихся n, затем n строк, каждая из которых содержит фамилию, имя и три числа (оценки по трем предметам: математике, физике, информатике). Данные в строке разделены одним пробелом. Оценки принимают значение от 1 до 5.

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

Примеры

№	Входные данные	Выходные данные
1	3 Yakovlev Ivan 5 5 5 Yapryntsev Aleksey 5 5 5 Kozlov Georgiy 5 5 5	Yakovlev Ivan Yapryntsev Aleksey Kozlov Georgiy