На шахматной доске размером n × m в поле с координатами (a, b) стоит одинокий слон. Определите количество полей, на которые он может переместиться за один ход. Напомним, что шахматный слон может за один ход переместиться на любое расстояние по любой из четырех диагоналей.
Формат входных данных
Единственная строка входного файла содержит четыре натуральных числа, записанных через пробел: n, m, a и b.
Формат выходных данных
Выведите одно неотрицательное целое число - количество различных ходов слона.
Антон - автор задач по спортивному программированию. Он живет на Дальнем Востоке и для организации олимпиад по информатике использует тестирующую систему ДВФУ. Сформировав пакет с очередной задачей, Антон загружает её на сервер в свою папку и управляет ею через страницу web-интерфейса.
Иногда Антону становится интересно, сколько всего задач он уже придумал? К сожалению, удобной нумерации задач на странице нет (каждой задаче можно назначить букву английского алфавита, но при большом количестве задач это не помогает). Поэтому Антон пользуется таким приемом: он выбирает из раскрывающегося списка число k - количество задач, которое будет отображаться на одной странице. После этого он переходит по ссылке на последнюю страницу с задачами (пусть ее номер будет x) и считает количество задач на этой странице y. Осталось посчитать общее количество задач по формуле k ⋅ (x − 1) + y.
На рисунке выше Антон выбрал представление по 10 задач на одной странице, перешел на последнюю из 17 страниц и увидел на ней 5 задач. По формуле 10 ⋅ 16 + 5 он определил, что всего загружено 165 задач. Поскольку умножает Антон мгновенно, а считает задачи медленно, помогите ему выбрать такое k, чтобы количество задач на последней странице y было как можно меньше.
Формат входных данных
Первая строка входного файла содержит два натуральных числа, записанных через пробел: n - общее количество придуманных Антоном задач (сам Антон его не знает) и m - количество способов выбрать число k. В следующей строке через пробел в порядке возрастания расположены m натуральных чисел ki.
Формат выходных данных
Выведите одно натуральное число, содержащееся во второй строке входных данных, при выборе которого Антон увидит наименьшее число своих задач на последней странице. Если подходящих чисел несколько - выведите наибольшее.
Ограничения
1 ≤ n ≤ 109
1 ≤ m ≤ 105
1 ≤ ki ≤ 109
n ≤ km
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примеру
Минимальное возможное количество задач на последней странице равно пяти. Это число можно получить, выбрав представление по 10, 20 или 40 задач на одной странице. Наибольшее из этих чисел: 40.
Тимофею очень нравится его имя, особенно первая буква - Т. Он привык рисовать её разными способами, лепить из пластилина и даже вырезать лобзиком из фанеры.
Однажды на уроке информатики, когда весь класс изучал табличный процессор, Тимофей по привычке раскрасил ячейки электронной таблицы в форме буквы Т. Затем он залил другим цветом все ячейки, имеющие общую сторону или угол с уже закрашенными ячейками. Затем выбрал другой цвет и снова залил другим цветом все ячейки, имеющие общую сторону или угол с уже закрашенными ячейками. Получилось красиво!
Подошедший учитель вернул Тимофея в рабочее состояние вопросом - а сколько ячеек таблицы нужно будет залить цветом при n-ой закраске? Тимофей вздохнул, закрыл электронную таблицу и запустил свой любимый Code::Blocks.
Сможете ли Вы опередить Тимофея в решении этой задачи?
Формат входных данных
В единственной строке через пробел записаны три натуральных числа n, x, y - порядковый номер закраски, размер шляпки и ножки начальной буквы Т. Гарантируется, что x - нечетное и шляпка лежит на ножке точно посредине. Высота шляпки и ширина ножки - одна ячейка.
Формат выходных данных
Выведете одно натуральное число - ответ на задачу. Считайте, что рабочий лист электронной таблицы бесконечен во все стороны.
Ограничения
1 ≤ n ≤ 109
3 ≤ x ≤ 99
1 ≤ y ≤ 100
Система оценки и описание подзадач
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Подзадача 1: 0 ≤ n ≤ 105, баллы: 30.
Подзадача 2: нет дополнительных ограничений, баллы: 70.
Из окна своей квартиры Тимофей наблюдает, как несколько молодых людей спортивного телосложения устроили на тротуаре розыгрыш денежных призов. Они собирают с желающих поиграть прохожих взнос за игру, а потом запускают лототрон.
Лототрон представляет собой заполненный n шарами лотерейный барабан треугольной формы. Каждый шар имеет уникальный номер от 1 до n. Шары вынимают снизу по одному, и на освободившееся место опускается один из двух шаров, находящихся выше, на освободившееся место опускается один из двух шаров, находящихся еще выше, и так далее. Если над освободившимся местом находится всего один шар - опускается он. Когда над освободившимся местом больше нет шаров, организаторы приступают к извлечению снизу нового шара.
Перед игрой лототрон заполняют шарами и несколько раз раскручивают, поэтому начальная расстановка шаров в барабане случайна. В игре побеждает игрок, верно указавший, какой шар будет извлечен k-м по счету. Спустя несколько раундов Тимофей заметил интересную особенность: на свободное место из двух шаров сверху всегда опускается шар с большим номером, а это значит, что последовательность извлечения шаров однозначно определяется их исходной расстановкой в лототроне. Поскольку в игре постоянно побеждают одни и те же "случайные" прохожие, Тимофей понял, что они пользуются заранее составленной компьютерной программой в своем смартфоне, позволяющей им быстро определять последовательность извлечения шаров. А Вы сможете составить такую программу?
Формат входных данных
В первой строке входного файла через пробел записаны два целых числа n и k - количество шаров в барабане и количество шаров, которые будут извлечены.
Во второй строке через пробел записаны n последовательных натуральных чисел от 1 до n - начальная расстановка шаров в барабане. Первый по счету шар лежит в нижнем (первом) ряду барабана, над ним (во втором ряду слева направо) - второй и третий, над ними в том же порядке шары с четвертого по шестой и так далее. Последний ряд может быть неполным, в этом случае шары в этом ряду лежат подряд вплотную к левому краю барабана.
Формат выходных данных
В единственной строке выходного файла запишите одно натуральное число - номер шара, который будет извлечен k-м по счету.
Ограничения
1 ≤ k ≤ n ≤ 1000.
Система оценки и описание подзадач
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Подзадача 1: k = 2, баллы: 10.
Подзадача 2: k = 3, баллы: 20.
Подзадача 3: нет ограничений, баллы: 70.
Пояснения к примеру 1
На первом шаге снизу извлекается шар номер 3. На освободившееся место "претендуют" два шара: 2 и 4. Вниз переходит шар номер 4 - его номер больше. На место этого шара "претендуют" два шара: 6 и 1. Вниз переходит шар номер 6 - его номер больше. Над свободным местом находится единственный шар номер 8 - он переходит вниз.
На втором шаге снизу извлекается шар номер 4. На освободившееся место "претендуют" два шара: 2 и 6. Вниз переходит шар номер 6. На место этого шара "претендуют" два шара: 4 и 1. Вниз переходит шар номер 4. Над свободным местом больше шаров нет.
Таким же образом будут последовательно извлечены шары с номерами 6, 8, 2, 7 и 5. Восьмым по счету будет шар номер 1.
После окончания уроков две ученицы Даша и Ксюша пришли в кабинет математики на консультацию. На доске они увидели число 1121321321.
- Смотри, какое интересное число! Несмотря на его длину в нём всего три различные цифры - один, два и три.
- Давай, пока Ольга Владимировна не пришла, запишем под этим числом своё. А получим мы его так: возьмём первую и вторую цифры исходного числа и запишем под ними новую. Причем если две верхние цифры одинаковые, то новая цифра будет ей равна. А если две верхние цифры различные, то нижняя цифра должна быть не равна никакой из верхних.
- То есть, если, например, две верхних цифры - тройки, то пишем под ними тройку... А если сверху тройка и двойка - пишем единицу?
- Точно! Потом возьмём вторую и третью цифру исходного числа и проделаем с ними ту же самую процедуру, потом - третью и четвертую, и так далее, пока цифры не закончатся.
- Давай, всё равно, пока ждем... Тем более, что наше новое число будет на одну цифру короче исходного.
И вот, что у девочек получилось...
- Давай следующие числа получим! Интересно, какой цифрой всё закончится?
Числа росли одно под другим, работа кипела, мел крошился... И вдруг уверенный голос Ольги Владимировны за их спинами произнес: "Я знаю, какая цифра окажется последней!"
Формат входных данных
Единственная строка входного файла содержит исходное число n. Гарантируется, что в его записи используются только три цифры: 1, 2 и 3.
Формат выходных данных
Выведите одну цифру - 1, 2 или 3, из которой будет состоять последнее число.
Ограничения
1 ≤ n < 10100000
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n < 10100, получат не менее 50 баллов.
Пояснение к примеру
В примере последовательно будут получены следующие числа:
