Вывод формулы

ID 31788. Снова спинеры

ID 26980. Бумага для олимпиады

ID 26979. Логические выводы

ID 21900. Кольцевая линия

В городе, в котором живут друзья Андрей и Борис, метро состоит из единственной кольцевой линии, вдоль которой на равном расстоянии друг от друга расположены n станций, пронумерованных от 1 до n. Участок линии метро между двумя соседними станциями называется перегоном.

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

Друзья заметили, что выполняется следующее условие: если загадать некоторую станцию X и выписать для нее два числа: Da — расстояние от станции, на которой живет Андрей, до станции X и Db — расстояние от станции, на которой живет Борис, до станции X, то полученная пара чисел [Da, Db] будет однозначно задавать станцию X.

Например, если n = 4, Андрей живет на станции 1, а Борис живет на станции 2, то станция 1 задается парой [0, 1], станция 2 — парой [1, 0], станция 3 — парой [2, 1] и станция 4 — парой [1, 2].

Их одноклассник Сергей живет в соседнем городе и не знает, на каких станциях живут Андрей и Борис. Чтобы найти друзей, он заинтересовался, сколько существует вариантов пар станций A, B, таких что если Андрей живет на станции A, а Борис — на станции B, то выполняется описанное выше условие.

Требуется написать программу, которая по числу станций n на кольцевой линии определяет искомое количество вариантов.

Формат входного файла
Первая строка входного файла содержит одно целое число n (3 ≤ n ≤ 40 000).
Формат выходного файла
Выходной файл должен содержать одно число — искомое количество вариантов.

Примеры входных и выходных файлов

ID 21886. Выбор зала

Для проведения церемонии открытия олимпиады по информатике организаторы осуществляют поиск подходящего зала. Зал должен иметь форму прямоугольника, длина каждой из сторон которого является целым положительным числом.
Чтобы все участники церемонии поместились в зале, и при этом он не выглядел слишком пустым, площадь зала должна находиться в пределах от A до B квадратных метров, включительно.
Чтобы разместить на стенах зала плакаты, рассказывающие об успехах школьников на олимпиадах, но при этом не создать ощущения, что успехов слишком мало, периметр зала должен находиться в пределах от C до D метров, включительно.
Прежде чем сделать окончательный выбор, организаторы олимпиады решили просмотреть по одному залу каждого подходящего размера. Залы с размерами Y × Z и Z × Y считаются одинаковыми. Чтобы понять необходимый объем работ по просмотру залов организаторы задались вопросом, сколько различных залов удовлетворяют приведенным выше ограничениям. Требуется написать программу, которая по заданным A, B, C и D определяет количество различных залов, площадь которых находится в пределах от A до B, а периметр — от C до D, включительно.

Формат входного файла
Входной файл содержит четыре разделенных пробелами целых числа: A, B, C и D (1<=A<=B<=10⁹ , 4<=C<=D<=10⁹ ).
Формат выходного файла
Выходной файл должен содержать одно число — искомое количество залов.

Ввод:
2 10 4 8
Вывод:
3

Пояснения к примеру
В примере ограничениям удовлетворяют залы следующих размеров: 1 × 2, 1 × 3, 2 × 2

ID 32971. Комета Бармалея

ID 32977. Выборы в USA

ID 33144. Два измерения

ID 31789. Не про спиннеры

Программа должна вывести одно число – количество прямоугольников, которые можно вырезать из данного листа бумаги (весь лист целиком также считается одним из возможных прямоугольников).
 

Ввод	Вывод	Примечание
2 2	9
3 1	6

 

ID 27061. Формула - 3

Напишите программу, которая вычисляет значение y.

ID 27060. Формула - 4

Напишите программу, которая вычисляет значение y.

Примеры

ID 27059. Формула - 5

Напишите программу, которая вычисляет значение y.

Примеры

ID 27058. Формула - 6

Напишите программу, которая вычисляет значение y.

Примеры

ID 33593. Шнурки

Обувная фабрика собирается начать выпуск элитной модели ботинок. Дырочки для шнуровки будут расположены в два ряда, расстояние между рядами равно a, а расстояние между дырочками в ряду b. Количество дырочек в каждом ряду равно N. Шнуровка должна происходить элитным способом “наверх, по горизонтали в другой ряд, наверх, по горизонтали и т.д.” (см. рисунок). Кроме того, чтобы шнурки можно было завязать элитным бантиком, длина свободного конца шнурка должна быть l. Какова должна быть длина шнурка для этих ботинок?

Формат входных данных
Программа получает на вход четыре натуральных числа a, b, l и N.

ID 33525. Улица

По одну сторону улицы находятся дома с нечётными номерами (1, 3, 5, …), по другую сторону – с чётными (2, 4, 6, …). Дом № 1 находится напротив дома № 2, дом № 3 – напротив дома № 4 и т. д. До соседнего дома нужно идти вдоль по улице одну минуту, неважно, с какой стороны улицы он находится (то есть от дома № 1 нужно идти одну минуту как до дома № 3, так и до дома № 4). До дома, стоящего напротив, идти не нужно.



Человек вышел на улицу из дома номер A и должен дойти до дома номер B. Определите, сколько минут ему нужно идти вдоль по улице. Программа получает на вход два различных целых положительных числа A и B, не превосходящие 2×10⁹ , – номера домов. Программа должна вывести одно число – искомое количество минут.

Входные данные
Программа получает на вход два различных целых положительных числа A и B,не превосходящие 2×10⁹, – номера домов.

Выходные данные
Программа должна вывести одно число – искомое количество минут.

Примеры

ID 23575. Периметр треугольника

С клавиатуры вводятся два целых числа - катеты прямоугольного треугольника. Напишите программу определения периметра такого треугольника.
 

Пример

ID 23574. Гипотенуза треугольника

С клавиатуры вводятся два целых числа - катеты прямоугольного треугольника. Напишите программу определения гипотенузы такого треугольника.
 

Пример

ID 33649. Периметр прямоугольника и длина диагонали

С клавиатуры вводятся два целых числа - стороны прямоугольника. Напишите программу нахождения его периметра и длины диагонали. Выведите в первой строке периметр прямоугольника, во второй строке - длину его диагонали.
 

Пример

ID 31924. Лифт

ID 33580. *Король-пекарь

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

Формат входных данных
Первая строка содержит число A – сторону одного квадрата кухонного фартука. Вторая и третья строки - числа X и Y – координаты левого нижнего угла картины. Четвёртая и пятая строки - числа W и H – ширина и высота картины. Ось OX направлена вправо, ось OY направлена вверх. Левый нижний угол одного из квадратов кухонного фартука находится в начале координат. Все числа целые, не превосходящие 2×10⁹ , числа A, W, H – положительные, числа X и Y – положительные или равны 0. Стороны картины параллельны осям координат.

Формат выходных данных
Вывести одно число – количество плиток, полностью или частично закрытых картиной.
Квадрат считается закрытым картиной, если пересечение картины и квадрата имеет ненулевую площадь, то есть касание картины и квадрата не считается перекрытием.

Примечание

ID 33692. Полоски радуги

В школе  № 2007 на уроке информатики в системе SilverTests Васе попалась следующая задача: «В  младшей группе одного объединённого детского сада воспитательница  изучала с детишками  порядок цветов радуги. Она отыскала семь соответствующих цветных мелков и начала рисовать полоски, не нарушая последовательности цветов.  Начала она с красной полоски. Когда доходила до фиолетовой полоски, опять рисовала  красную. Воспитательница  успела нарисовать N полосок, когда у неё закончились  мелки. Напишите программу, которая вычисляет количество полосок каждого цвета».  Вася взялся писать программу, но тут обнаружилось, что на клавиатуре отсутствует клавиша с буквой  «i». Помогите Васе написать программу с учётом этого обстоятельства.

Входные данные: Вводится одно целое положительное число N > 0.
Выходные данные: Выведите ответ на задачу.

Если в коде программы встречается буква «i» система выдаст сообщение:  Использование запрещенных операторов
 
Примеры

ID 37015. Совпадение стрелок

На вход программе подаются два целых числа n, m, каждое в отдельной строке \(0<n<=12, 0<=m<60\) , указывающие момент времени "n часов m минут". Определите наименьшее число полных минут, которое должно пройти до того момента, когда часовая и минутная стрелки ни циферблате совпадут, не обязательно на каком-то делении. Вещественную арифметику не использовать.

Задачу необходимо решить без использования условных операторов (в том числе без тернарного оператора ?: в С++) и\или циклов. Кроме того, нельзя использовать операции сравнения и логический (булевский) тип данных.

Примеры

ID 38468. Чётные – нечётные

Маша любит чётные числа, а Миша – нечётные. Поэтому они всегда радуются, если встречают числа, которые им нравятся.
Сегодня им встретились все целые числа от A до B включительно. Маша решила посчитать сумму всех чётных чисел от A до B, а Миша – сумму всех нечётных, после чего они начали спорить, у кого получилась сумма больше. Помогите им – найдите разность
между суммой Маши и суммой Миши.
Программа получает на вход два целых положительных числа A и B, не превосходящие 2×10⁹.
Программа должна вывести одно число – разность между суммой чётных чисел и суммой нечётных чисел от A до B.

Примеры

ID 38478. Покупка

Ручка стоила K рублей. Первого сентября стоимость ручки увеличилась ровно на P процентов. Определите, сколько ручек можно купить на S рублей после подорожания.
Программа получает на вход три целых положительных числа. Первое число K – стоимость ручки в рублях до подорожания. Второе число P – величина подорожания ручки
в процентах. Третье число S – имеющаяся сумма денег. Числа K и S не превосходят 10⁷ , число P не превосходит 100.
 

Примеры

ID 38504. Между А и В

Вам даны неотрицательные целые числа a и b (a<=b) и положительное целое число x. Сколько целых чисел от a до b включительно делятся на x?

Входные данные
В одной строке задаются три числа a, b и x (\(0<=a<=b<=10^{18}\), \(1<=x<=10^{18}\)).

Выходные данные
Выведите на экран ответ на задачу.
 

Примеры

ID 38555. Черепашка

Черепашка ползет по полу, который уложен квадратной плиткой со стороной A см. Начало пути Черепахи в точке X. Черепашка успела проползти расстояние D см, прежде чем хозяин взял ее на руки. Определите сколько клеток (частично или целых) успела проползти Черепашка.

Входные данные
Первая строка содержит число A – длина стороны одной плитки. Вторая строка содержит число X - координата точки, с которой Черепашка начала свой путь. Третья строка - число D - расстояние, которое проползла Черепаха. Ось OX направлена вправо. Крайняя плитка в ряду, по которому ползет Черепашка находится в начале координат. Все числа целые, не превосходящие \(2\cdot10^9 \), числа A, D – положительные, число X – положительное или равно 0.

Выходные данные
Вывести одно число – количество плиток, которые Черепашка полностью или частично успела проползти.
Считается, что Черепашка проползла плитку, если условно проведенная линия пути Черепашки имеет ненулевую длину, то есть касание линии пути и края плитки не считается.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	10 15 35	4	Сторона плитки (сторона клетки на рисунке) А = 10. Черепашка начала движение с координаты Х = 15, и прошла 35. Черепаха прошла полностью или частично 4 плитки.

ID 38578. Оставшееся время

Громозека любит соревнования по программированию. Сегодня он примет участие в конкурсе в STCoder. На этой площадке используются 24-часовые часы. Например, 21:00. обозначается как «21 o'clock».
Текущее время - A часов, а соревнование начнется ровно через B часов. Определите время начала соревнования? Ответ дайте в 24-часовом формате.

Входные данные
Во входной строке содержится два целых числа A и B (\(0<=A,B<=23\)), записанных через один пробел.

Выходные данные
Выведите час начала конкурса в 24-часовом формате.
 

Примеры

ID 38629. Минимизация

Имеется последовательность длины N: A1, A2, ..., AN. Изначально эта последовательность представляет собой перестановку 1, 2, ..., N. В этой последовательности Алиса может выполнить следующую операцию:
1) выбрать K последовательных элементов в последовательности;
2) затем заменить значение каждого выбранного элемента минимальным значением среди выбранных элементов.
Алиса хочет уравнять все элементы в этой последовательности, повторяя указанную выше операцию некоторое количество раз.
Найдите минимальное количество необходимых операций.
Можно доказать, что при ограничениях этой проблемы эта цель всегда достижима.

Входные данные
В первой строке задаются два целых числа N и K (2<=K<=N<=100000). Во второй строке задается последовательность целых чисел A1, A2, ..., AN - перестановка чисел от 1 до N (каждое число в последовательности различно, 1<=A_i<=N).

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

Примеры

ID 38667. Ускорение Незнайки

Незнайка тренировался у Торопыжки быстрее ходить. До тренировки он проходил путь длиной S метров за t1 секунд. После тренировки скорость Незнайки увеличилась на P%. Напишите программу, которая определяет, какой путь (в метрах) будет проходить Незнайка за t2 секунд после тренировки с Торопыжкой.

Входные данные
На вход четыре целых числа: S (1<=S<=100), t1(1<=t₁<=100), P (1<=P<=100)  и t2 (1<=t₂<=100).

Выходные данные
Выведите одно число - ответ на задачу.
 

Пример

ID 38668. Автомобили Винтика и Шпунтика

Винтик и Шпунтин тестировали новые автомобили. Расстояние вокруг Цветочного города автомобиль Винтика проехал за t1 секунд, спидометр всю дорогу показывал скорость V м/с. Автомобиль Шпунтика такое же расстояние вокруг Цветочного города прошел за t2 секунд, при этом спидометр у Шпунтика был сломан. Помогите Шпунтику определить с какой скоростью (в м/с) он ехал.

Входные данные
На вход 3 целых числа:  t1(1<=t₁<=100), V(1<=V<=100)  и t2 (1<=t₂<=100).

Выходные данные
Выведите одно число - ответ на задачу.
 

Пример

ID 38762. Камень-Ножница-Бумага. Без "Ножниц"

Незнайка и его друг Гунька играют в игру. Игра состоит из N ходов. На каждом ходу каждый игрок играет одним из двух жестов, Камень и Бумага, как в «Камень-ножницы-бумага», при следующих условиях:
- После каждого хода
(количество раз, когда игрок играл Бумагу) <= (количество раз, когда игрок играл Камень).
- Счет каждого игрока рассчитывается по формуле:
(количество ходов, на которых игрок выигрывает) - (количество ходов, на которых игрок проигрывает),
где результат каждого хода определяется по правилам «камень-ножницы-бумага».

Для тех, кто не знаком с игрой "Камень-нужница-бумага": если один игрок играет Камень, а другой играет Бумагу, последний игрок выиграет, а первый проиграет. Если оба игрока играют одним и тем же жестом, раунд считается ничейным, и ни один из игроков ни выиграет ни проиграет.

Используя волшебную палочку Незнайка смог предвидеть жест, который Гунька будет использовать в каждом из N ходов перед началом игры. Распланируйте жесты Незнайки на каждом шагу, чтобы максимизировать его счет.
Жест, который Гунька будет воспроизводить на каждом ходу, задается строкой s. Если i-й (1 <= i <= N) символ в s равен g, то Гунька будет играть "Камень" на i-м ходу. Аналогично, если i-й (1 <= i <= N) символ s в p, Гунька будет играть Бумага на i-м ходу.

Входные данные
На вход подается одна строка s длиной N. Каждый символ в строке s - это g или p. Жесты, представленные s, удовлетворяют условию игры.

Выходные данные
Выведите максимально возможный счет Незнайки.
 

Примеры

ID 39383. Белые клетки

Клетчатое поле состоит из белых клеток. Размер поля - H строк и W столбцов. Вам необходимо выбрать h строк и w столбцов и закрасить все ячейки, содержащиеся в этих строках или столбцах. Сколько белых клеток останется после закрашивания?

Входные данные
В первой строке записаны 2 числа: H и W (1 <= H, W <= 20). Во второй строке записаны 2 числа: h и w (1 <= h <= H, 1 <= w <= W).

Выходные данные
Выведите ответ на задачу.
 

Примеры

ID 39505. Часовое дерево

Новый амбар Фермера Джона состоит из N комнат (2 ≤ N ≤ 2500), последовательно пронумерованных 1…N, и N−1 коридоров. Каждый коридор соединяет пару комнат таким образом, что возможно пройти из лбой комнаты в любую через серию коридоров.
Каждая комната в амбаре имеет круглые часы на стене со стандартным размещением цифр 1…12 на лицевой стороне. Однако на этих часах имеется только одна стрелка, которая всегда показывает точно на одно из целых чисел (она никогда не показывает между двумя из этих чисел).

Корова Беси хочет синхронизировать все часы в амбаре, чтобы они все показывали на число 12. Но со своим коровьим мышлением, каждый раз, когда она входит в комнату, она перемещает стрелку вперёд на одну позицию. Например, если стрека показывала на 5, Беси переводит стрелку на 6. Если часы указывали на 12, она переводит стрелку на 1. Если Беси входит в комнату несколько раз, она переводит стрелку при каждом входе.

Определите номера комнат, в которых Беси может начинать путешествие по амбару чтобы установить все стрелки на 12. Заметим, что Беси не переводит стрелку в стартовой комнате в начале пути и переводит при каждом последующем входе в неё. Стрелки сами по себе не двигаются. Беси входя в коридор должна дойти до конца и войти в комнату в конце коридора. Она не может повернуть назад внутри коридора, чтобы снова войти в комнату из которой вышла.

Входные данные
Первая строка ввода содержит N. Следующая строка содержит N целых чисел, каждое в интервале 1…12, указывающих начальные положения стрелок в каждой комнате. Каждая из следующих N−1 строк описывает коридор двумя целыми числам a и b, каждое в интервале 1…N, и задающих номера комнат, соединённых этим коридором.

Выходные данные
Выведите номера комнат, в которых Беси может начинать, чтобы установить все часы на 12.

Примеры

4
11 10 11 11
1 2
2 3
2 4

ID 39513. Треугольники - 2

Фермер Джон хочет создать треугольное пастбище для своих коров.
Всего имеется N столбов забора (3 ≤ N ≤ 10⁵) как различных (X₁,Y₁)…(X_N,Y_N) точек на карте фермы. Он может выбрать три из них чтобы сформировать вершины треугольного пастбища, но так чтобы одна из сторон была параллельна оси x, а другая - параллельно оси y.

Какова сумма площадей всех возможных пастбищ, которые может сформировать ФД?

Входные данные
Первая строка содержит N.
Каждая из последующих N строк содержит два целых числа Xi и Yi, каждое в интервале −10⁴…10⁴ включительно, описывающих положение столба.

Выходные данные
Поскольку сумма площадей может быть числом не целым и очень большим, выведите остаток от деления удвоенной суммы площадей на 10⁹+7.

Примеры

4
0 0
0 1
1 0
1 2

ID 39514. Раз-два-три-четыре-пять корову поменять

N коров (1 ≤ N ≤ 10⁵) Фермера Джона стоят в ряд. i-ая корова слева имеет метку i (1 ≤ i ≤ N).
ФД дал коровам M пар целых чисел s (L₁,R₁)…(L_M,R_M), где 1 ≤ M ≤ 100. Затем он сказал коровам повторить ровно K (1 ≤ K ≤ 10⁹) раз процесс из M шагов:

Для каждого i от 1 до M:
Последовательность коров на позициях Li…Ri слева реверсивно меняют свой порядок.
Выведите метки всех коров слева направо для каждого i, (1 ≤ i ≤ N) после завершения описанного процесса.

Входные данные
Первая строка содержит числа N, M, K. Для каждого 1 ≤ i ≤ M строка i+1 содержит L_i и R_i, два целых числа в интервале 1…N, где L_i<R_i.

Выходные данные
На i-ой строке вывода, выведите i-ый элемент массива после выполнения всех инструкций K раз.

Примеры

7 2 2
2 5
3 7

1
2
4
3
5
7
6

ID 27221. Bovine Genomics №2

ID 39515. Три четыре пять корову поменять

N  коров (1 ≤ N ≤ 100) Фермера Джона выстроены в ряд. i-ая корова слева имеет метку i, для всех 1≤i≤N.
ФД приказал коровам повторить ровно K (1 ≤ K ≤10⁹) раз следующий двухшаговый процесс:

Последовательность коров в позициях A1…A2 слева реверсивно меняют свой порядок (1≤A₁<A₂≤N).
Затем последовательность коров в позициях B1…B2 слева реверсивно меняют свой порядок (1≤B₁<B₂≤N).
Выведите получившийся порядок коров для всех i 1 ≤ i ≤ N после выполнения этого процесса ровно K раз.


Входные данные
Первая строка содержит N и K. Вторая строка содержит A₁ и A₂, третья строка содержит B₁ и B₂.
Выходные данные
На i-ой строке выведите метку i-ой коровы слева после завершения процесса всех обменов.

Примеры

7 2
2 5
3 7

1
2
4
3
5
7
6

ID 39517. Треугольники

Фермер Джон хочет создать треугольное пастбище для своих коров.
Всего имеется N столбов забора (3 ≤ N ≤ 100) как различных (X₁,Y₁)…(X_N,Y_N) точек на карте фермы. Он может выбрать три из них чтобы сформировать вершины треугольного пастбища, но так чтобы одна из сторон была параллельна оси x, а другая - параллельно оси y.

Какова сумма площадей всех возможных пастбищ, которые может сформировать ФД?

Входные данные
Первая строка содержит N.
Каждая из последующих N строк содержит два целых числа Xi и Yi, каждое в интервале −10⁴…10⁴ включительно, описывающих положение столба.

Выходные данные
Поскольку сумма площадей может быть числом не целым и очень большим, выведите остаток от деления удвоенной суммы площадей на 10⁹+7.

Примеры

4
0 0
0 1
1 0
1 2

ID 39535. Голодная пешка

Громозека уважает игры на шахматной доске. На обычной доске размером 8х8 у Громозеки стоит голодная пешка. Голодная пешка каждым ходом съедает какую-либо фигуру соперника (т.е. она может пойти по диагонали вперед на 1 клетку вправо или влево, назад пойти она не может). Громозека, не глядя на доску, научился определять, может ли голодная пешка попасть с одной клетки доски на другую. Превращаться в ферзя голодной пешке нельзя.
Напишите программу, с помощью которой вы могли бы также легко проверить Громозеку.

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

Выходные данные
Выведите слово YES (заглавными буквами), если голодная пешка может попасть из первой клетки во вторую, и NO в противном случае.
Доска имеет размер 8x8, вертикали нумеруются маленькими латинскими буквами от a до h, горизонтали - числами от 1 до 8. Исходная и конечная клетки не совпадают.
 

Примеры

ID 39551. Коровы в стойле

У Фермера Джона есть N коров (1 ≤ N ≤ 20) с высотами a₁…a_N. Его амбар имеет N стойл с максимальными высотами b₁…b_N (поэтому например, b₅=17 означает, что коров с высотой не более 17 можно разместить в стойле 5). Сколькими различными способами ФД может разместить коров по стойлам, так чтобы ограничение по высоте было выполнено для каждого стойла.

Входные данные
Первая строка содержит N. Вторая строка содержит N разделённых одиночными пробелами чисел a₁, a₂,…,a_N. Третья строка содержит N разделённых одиночными пробелами чисел b₁,b₂,…,b_N. Все величины - целые числа в интервале [1,10⁹].

Выходные данные
Количество способов, которыми ФД может разместить коров в стойлах, так чтобы для каждого стойла был удовлетворён лимит по высоте. Заметьте, что ответ может быть очень большим, поэтому для него требуется использовать 64-битную целую переменную, такую как "long long" в C++.

Примеры

4
1 2 3 4
2 4 3 4

ID 39560. Еще больше странных фотографий

Фермер Джон фотографирует N своих коров (2≤N≤1000).
Каждая корова имеет целое число - "ID породы" в интервале 1…100. ФД разбить всех коров на несвязные группы (другими словами, поместить каждую корову ровно в одну группу) и затем выставить группы так, чтобы сумма "ID породы" коров в первой группе была чётной, во второй - нечётной и т.д., чередуя чётные и нечётные.

Какое максимальное количество групп может сформировать ФД?

Входные данные
Первая строка ввода содержит число N. Следующая строка содержит N разделённых пробелом целых чисел, представляющих "ID породы".
Выходные данные
Максимально возможное количество групп на фото ФД. Можно доказать, что хотя бы одна группа будет всегда.

Примеры

7
1 3 5 7 9 11 13

7
11 2 17 13 1 15 3

ID 39669. Хэш двойной строки

Вам дано t запросов, в каждом из которых вам дана строка s, состоящая из строчных латинских букв, число p и число mod.
Для каждого запроса вычислите полиномиальный хэш с основанием p по модулю mod от строки, являющейся строкой s, где каждая буква продублирована. То есть, если s = "isaac", то нужно посчитать хэш от строки "iissaaaacc".

Входные данные:
В первой строке дается число t - количество запросов.
Далее идет t строк, в каждой из которых через пробел даны s (1 <= |s| <= 20), p (1 <= p <= 10⁵) и mod (1 <= mod <= 10⁸).

Выходные данные:
Выведите ответы на запросы, каждый в отдельной строке.

Пример:
 

ID 41227. Мощный массив

Имеется массив натуральных чисел a₁, a₂, ..., a_n. Рассмотрим некоторый его подмассив a_l, a_l + 1, ..., a_r, где 1 ≤ l ≤ r ≤ n, и для каждого натурального числа s обозначим через K_s число вхождений числа s в этот подмассив. Назовем мощностью подмассива сумму произведений K_s·K_s·s по всем различным натуральным s. Так как количество различных чисел в массиве конечно, сумма содержит лишь конечное число ненулевых слагаемых.

Необходимо вычислить мощности каждого из t заданных подмассивов.

Входные данные
Первая строка содержит два целых числа n и t (1 ≤ n, t ≤ 200000) — длина массива и количество запросов соответственно.
Вторая строка содержит n натуральных чисел ai (1 ≤ a_i ≤ 10⁶) — элементы массива.
Следующие t строк содержат по два натуральных числа l и r (1 ≤ l ≤ r ≤ n) — индексы левого и правого концов соответствующего подмассива.

Выходные данные
Выведите t строк, где i-ая строка содержит единственное натуральное число — мощность подмассива i-го запроса.

Примеры:
 

ID 41230. Лабораторные столы

На кафедру "Прикладной информатики" университета N в новом учебном году набрали три группы первокурсников. Для практических занятий необходимо оборудовать новую аудиторию лабораторными столами. За каждым таким столом могут сидеть не более четырех студентов, причем все студенты обязаны быть из одной группы. Аудитория имеет возможность одновременно разместить студентов сразу трех групп одновременно.
Определите минимальное количество столов, которые необходимо закупить.

Входные данные
Программа получает на вход три натуральных числа (по одному числу в строке): количество студентов каждой из трех групп.

Выходные данные
Выведите ответ на задачу.
 

Примеры

ID 41231. Разность времен

Даны значения двух моментов времени, принадлежащих одним и тем же суткам: часы, минуты и секунды для каждого из моментов времени. Известно, что второй момент времени наступил не раньше первого. Определите, сколько секунд прошло между двумя моментами времени.

Входные данные
Программа на вход получает три целых числа — часы, минуты, секунды, задающие первый момент времени и три целых числа, задающих второй момент времени.

Выходные данные
Выведите число секунд между этими моментами времени.
 
 

Примеры

1
1
1
2
2
2

3661

1
2
30
1
3
20

50

ID 39242. Машина для печенья

Машина для изготовления печенья производит B печенья в следующие моменты времени: A секунд, 2A секунд, 3A секунд и каждое последующее число, кратное A секундам после включения. Определите сколько печенья будет изготовлено машиной к моменту времени T+0,5 секунд после включения.

Входные данные
Программа получает на вход одну строку, содержащую три числа A, B и T.  1 <= A, B, T <= 20, A <= T. Все числа целые положительные.

Выходные данные
Выведите одно число - ответ на задачу.
 

Примеры

ID 46945. Приключения Максимуса

Однажды Максимус услышал о загадочной пещере, которая находится на вершине высокой горы. Говорят, что в этой пещере скрывается невероятное сокровище. Максимус преодолевает опасности и достигает пещеры. Но в пещере его встречает Старец, который просит по заданным двум числам num и t назвать ему максимальное супер-число. Число x называется супер-числом, если его можно сделать равным num, применяя следующую операцию t раз:

• увеличьте или уменьшите x на 1 и одновременно увеличьте или уменьшите num на 1.

• 1 <= num, t <= 50

Примеры

ID 47203. Улица

По одну сторону улицы находятся дома с нечётными номерами (1, 3, 5, …), по другую сторону – с чётными (2, 4, 6, …). Дом № 1 находится напротив дома № 2, дом № 3 – напротив дома № 4 и т. д. До соседнего дома нужно идти вдоль по улице одну минуту, неважно, с какой стороны улицы он находится (то есть от дома № 1 нужно идти одну минуту как до дома № 3, так и до дома № 4). До дома, стоящего напротив, идти не нужно.



Громозека вышел на улицу из дома номер A и должен дойти до дома номер B. Определите, сколько минут ему нужно идти вдоль по улице.

Запрещено использовать какие-либо алгоритмические конструкции для решения данной задачи. Можно использовать только арифметические операции (без использования встроенных функций).

Входные данные
Программа получает на вход два различных целых положительных числа A и B,не превосходящие 2×10⁹, – номера домов.

Выходные данные
Программа должна вывести одно число – искомое количество минут.

Примеры

ID 47205. Подъемник

•  если подъемник проезжает мимо этажа, на котором нажата кнопка вызова, и, при этом,  движется в подходящем направлении, то подъемник останавливается и в него можно зайти.

ID 47206. Поиграем в камушки

Магистр Максимус со своим верным другом фокусником Феликсом играют в игру камушки. Правила этой игры описаны ниже.

• Вначале на столе лежит куча камней.
• Ходы Максимуса и Феликса чередуются по очереди, причем Максимус всегда ходит первым.
• На каждом ходу тот, чья очередь подошла, убирает от 1 до 3 камней из кучи.
• Побеждает тот, кто уберет последний камень.

Примеры

ID 47308. Василий собирает ягоды

Медведь Василий собирает ягоды. Он будет счастлив, если ягод малины в его корзинке окажется не менее трети от общего числа ягод. Медведь Василий уже собрал N ягод, из них K штук малины. Василий уже изрядно устал собирать ягоды, поэтому помогите ему понять, какое минимальное число ягод малины ему необходимо собрать, чтобы быть счастливым. 


Входные данные
Программа получает на вход два целых числа N и K (N > 0, 0 ≤ K ≤ N, K<=10⁹, N<=2*10⁹), записанные в отдельных строках, — текущее количество ягод в корзинке медведя Василия и количество ягод малины в корзинке.

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

 

Примеры

ID 27118. Intelligence in Perpendicularia

There are only two directions in Perpendicularia: vertical and horizontal. Perpendicularia government are going to build a new secret service facility. They have some proposed facility plans and want to calculate total secured perimeter for each of them.
The total secured perimeter is calculated as the total length of the facility walls invisible for the perpendicularly-looking outside observer. The figure below shows one of the proposed plans and corresponding secured perimeter. 

ID 27115. Auxiliary Project

Anna has just finished her course project. She has a lot of seven-segment LED displays as leftovers and a small power source. Each display consumes power proportionally to the number of lit segments, e.g. ‘9’ consumes twice more power than ‘7’.


Anna wonders what is the maximum possible sum of digits she is able to achieve, if her power source is able to light n segments, and she wants to light exactly n segments.
Input
The single line of the input contains one integer n — the number of segments that should be lit (2 ≤ n ≤ 10⁶ ).
Output
Output a single integer — the maximum possible sum of digits that can be displayed simultaneously.

ID 27040. Время полета

ID 27027. Дилемма Кубратова

ID 23335. Денежная система (С, В')

ID 23334. Интересные числа (С', C)

ID 47969. Шнурки

Обувная фабрика собирается начать выпуск элитной модели ботинок. Дырочки для шнуровки будут расположены в два ряда, расстояние между рядами равно a, а расстояние между дырочками в ряду b. Количество дырочек в каждом ряду равно N. Шнуровка должна происходить элитным способом “наверх, по горизонтали в другой ряд, наверх, по горизонтали и т.д.” (см. рисунок). Кроме того, чтобы шнурки можно было завязать элитным бантиком, длина свободного конца шнурка должна быть l. Какова должна быть длина шнурка для этих ботинок?
Запрещено использовать операторы if, while, for, repeat-until (Паскаль)

Входные данные: Программа получает на вход четыре натуральных числа a, b, l и N.

ID 48040. Ферзь

Пётр любит шахматы и математику. Он знает, что самая мощная фигура в шахматах - это ферзь, потому что он ходит и как ладья, на все клетки на одной с ним вертикали или горизонтали, и как слон, на все клетки по диагоналям. Ферзя можно поставить на доску 8 X 8 так, чтобы он контролировал (то есть мог переместиться в эти клетки за один ход) целых 27 клеток доски!

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

Формат входных данных
Первая строка входных данных содержит целое число n (1 ≤ n ≤ 10⁹) - размер доски по вертикали.
Вторая строка входных данных содержит целое число m (1 ≤ m ≤ 10⁹) - размер доски по горизонтали.
Формат выходных данных

Программа должна вывести одно целое число - максимальное количество клеток, которое может контролировать ферзь на доске n x m.

Обратите внимание на то,  что ответ в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип long long в языке C++, тип int64 в Pascal, тип long в Java и C#).

Замечание
Второй пример из условия приведён на рисунке. Крестиками обозначены клетки, которые контролирует ферзь.

 

ID 45674. Два массива

Алиса со своим отцом профессором Селезневым записывают на листочке числа определенной последовательности. У Алисы каждый i-й член последовательности равен i², у профессора Селезнева i-й член последовательности равен i³. Они решили создать новую возрастающую последовательность путем объединения двух своих последовательностей. При этом, если в обоих последовательностях есть одинаковое число, то в новой последовательности оно присутствует только один раз. 

Алиса и профессор просят вас угадать i-е число в новой объединенной последовательности. 

В единственной строке входного файла дано натуральное число i (1 <= i <= 10⁷).

Выведите i-е число новой последовательности. 

Примеры

ID 48902. Василий собирает ягоды

Летовец набирает себе предметы, которые он будет изучать в текущем учебном году. Он будет счастлив, если количество его любимых предметов в учебном плане окажется не менее трети от общего числа предметов. Летовец уже выбрал N предметов, из них K любимых. Теперь он хочет посчитать, какое минимальное количество любимых предметов ему осталось выбрать, чтобы быть весь учебный год счастливым. 

Формат входных данных
Программа получает на вход два целых числа N и K (N > 0, 0 ≤ K ≤ N, K<=10⁹, N<=2*10⁹), записанные в отдельных строках, — текущее количество предметов и количество любимых предметов, которые Летовец уже выбрал.

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

Примечение
В примере всего предметов 27, из которых любимых 7.
Если в выбрать ещё 3 любимых предмета, то всего станет 30 предметов, из которых любимых будет 10.
 

ID 33121. Улучшение успеваемости

ID 33126. Старая книга

ID 34771. Плитка

Стена покрыта квадратной плиткой со стороной M см. На стену повесили картину, известны координаты левого нижнего угла картины, её ширина и высота. Определите количество плиток, которые оказались частично или полностью закрыты картиной.

Первая строка входных данных содержит число M – сторону плитки. Вторая и третья строки содержат числа X и Y – координаты левого нижнего угла картины. Четвёртая и пятая строки содержат числа W и H – ширину и высоту картины. Ось OX направлена вправо, ось OY направлена вверх. Левый нижний угол одной из плиток находится в начале координат. Все числа целые, не превосходящие 2×10⁹ , числа M, W, H – положительные, числа X и Y – положительные или равны 0.

Программа должна вывести одно число – количество плиток, полностью или частично закрытых картиной. Плитка считается закрытой картиной, если пересечение картины и плитки имеет ненулевую площадь, то есть касание картины и плитки не считается перекрытием.

 

ID 34773. Сажени, аршины, пяди, вершки

Древнерусская мера длины сажень состояла из трёх аршин. Один аршин делился на четыре пяди. Одна пядь состояла из 4 вершков.
Купец привез на рынок рулон сукна длиной N вершков, но для уплаты пошлины ему нужно указать длину сукна в саженях, аршинах, пядях и вершках. Помогите ему – переведите длину сукна, записанного в вершках в сажени, аршины, пяди и вершки.
Программа получает на вход одно натуральное число N, не превосходящее 2×10⁹ , – длину сукна в вершках.
Программа должна вывести 4 целых неотрицательных числа S, A, P, V – количество саженей, аршин, пядей и вершков, в сумме дающих ровно N вершков, при этом значение A должно быть меньше 3 (т. к. 3 аршина дают одну сажень), значение P должно быть меньше 4 (четыре пяди дают один аршин), значение V должно быть меньше 4 (четыре вершка дают одну пядь).
 

ID 34777. Замок

Замок имеет форму большого квадрата, составленного из N × N маленьких квадратиков. Внешние квадратики являются башнями, именно они играют основную роль в защите замка от неприятеля. Например, если замок имеет размер 4 × 4, то у него 12 башен (смотрите второй рисунок, башни на нем выделены серым цветом).

Замок охраняет K полков, которые необходимо разместить по башням. В одной башне можно разместить несколько полков, но при этом в каждой башне должен находиться хотя бы один полк, иначе неприятель легко захватит эту башню. Если все башни защищены, то неприятель выбирает для атаки одну из четырех сторон замка, которую защищает наименьшее число полков (то есть суммарное число полков во всех башнях данной стороны квадрата минимально).

Определите, как нужно разместить полки для наилучшей защиты замка.

Входные данные

Первая строка входных данных содержит число N — размер замка (2 ≤ N ≤ 100). Вторая строка входных данных содержит число K — количество полков, охраняющих замок (0 ≤ K ≤ 100).

Выходные данные

Выведите единственное число — количество полков на наименее укрепленной стороне замка при наилучшем размещении полков. Если имеющихся полков недостаточно для защиты всех башен, выведите число 0.

 

ID 50983. Составление МОШ

Для МОШ по информатике было придумано и подготовлено \(n\) задач. Всего в олимпиаде будут учавствовать \(k\) школьников. И вот до олимпиады осталась всего неделя! Но, как вы знаете, некий <<Турист>> очень любит придумывать задачи и потом давать их на разные олимпиады. А так как <<Турист>> ну уж очень умный, то он явно придумает и даст все задачи, которые придумало жюри МОШа. В рамках подготовки к олимпиаде, школьники будет решать задачи <<Туриста>>. Причём вы знаете, что каждый из участников прорешает за неделю не менее \(a\) и не более \(b\) задач из тех, что собираются дать на МОШ. Жюри даст на олимпиаду все задачи, которые не решал никто из участников ранее. Скажите минимальное и максимальное количество задач, которые могут быть даны на МОШ из заранее подготовленных.

Формат входных данных
В первой строке вводится число \(n\) \((1 \leqslant n \leqslant 10^9)\) — количество задач, подготовленных для МОШ по информатике.

Во второй строке вводится число \(k\) \((1 \leqslant k \leqslant 10^9)\) — число участников МОШ.

В третьей строке вводится число \(a\) \((1 \leqslant a \leqslant n)\) — минимальное число задач, которое прорешает каждый из участников в течение недели.

В третьей строке вводится число \(b\) \((a \leqslant b \leqslant n)\) — максимальное число задач, которое может прорешать каждый из участников в течение недели.

Формат выходных данных
Выведите два числа – минимальное и максимальное число задач, которые жюри может дать на МОШ.

ID 50988. Ещё одна акция - 2

В знаменитом магазине <<Двоечка>> продукты продаются всего два дня в неделю — понедельник и вторник — причём в разные дни по разным ценам. Вы захотели купить \(n\) килограммов картофеля на неделю. По понедельникам один килограмм картофеля стоит \(a\) рублей, а по вторникам — \(b\) рублей. Чтобы упростить работу кассирам, в <<Двоечке>> можно покупать только целое число килограммов.

Вам крупно повезло, ведь в <<Двоечке>> проходит акция: каждый понедельник за каждые \(m\) килограммов купленного картофеля дарят ещё один!

Найдите минимальную сумму, за которую можно приобрести хотя бы \(n\) килограммов картофеля на неделю.

Формат входных данных
В первой строке вводится целое число \(a\) \((1 \leqslant a \leqslant 10^9)\) — цена одного килограмма картофеля в понедельник.

Во второй строке вводится целое число \(b\) \((1 \leqslant b \leqslant 10^9)\) — цена одного килограмма картофеля во вторник.

В третьей строке вводится целое число \(n\) \((1 \leqslant n \leqslant 10^9)\) — желаемое количество килограммов картофеля.

В четвертой строке вводится целое число \(m\) \((1 \leqslant m \leqslant 10^9)\) — количество килограммов картофеля, участвующее в акции.

Формат выходных данных
Выведите одно целое число — минимальное число рублей, которое придется заплатить, чтобы купить хотя бы \(n\) килограммов картофеля.

Обратите внимание, что ответ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать и с типом int.

В первом примере выгодно купить один килограмм в понедельник за 5 рублей, получить еще один килограм в подарок и купить килограмм во вторник за 4 рубля. Купить три килограмма дешевле не получится.

Во втором примере выгодно купить три килограмма в понедельник и получить один килограмм в подарок.

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

В четвертом примере выгодно купить шесть килограммов в понедельник, получить по акции три килограмма и купить еще один килограмм во вторник.

ID 50989. Ещё одна акция

В знаменитом магазине <<Двоечка>> продукты продаются всего два дня в неделю — понедельник и вторник — причём в разные дни по разным ценам. Вы захотели купить \(n\) килограммов картофеля на неделю. По понедельникам один килограмм картофеля стоит \(a\) рублей, а по вторникам — \(b\) рублей. Чтобы упростить работу кассирам, в <<Двоечке>> можно покупать только целое число килограммов.

Вам крупно повезло, ведь в <<Двоечке>> проходит акция: каждый понедельник за каждые \(m\) килограммов купленного картофеля дарят ещё один!

Найдите минимальную сумму, за которую можно приобрести хотя бы \(n\) килограммов картофеля на неделю.

Формат входных данных
В первой строке вводится целое число \(a\) \((1 \leqslant a \leqslant 10^9)\) — цена одного килограмма картофеля в понедельник.

Во второй строке вводится целое число \(b\) \((1 \leqslant b \leqslant 10^9)\) — цена одного килограмма картофеля во вторник.

В третьей строке вводится целое число \(n\) \((\mathbf{1 \leqslant n \leqslant 10^6})\) — желаемое количество килограммов картофеля.

В четвертой строке вводится целое число \(m\) \((1 \leqslant m \leqslant 10^6)\) — количество килограммов картофеля, участвующее в акции.

Формат входных данных
Выведите одно целое число — минимальное число рублей, которое придется заплатить, чтобы купить хотя бы \(n\) килограммов картофеля.

Обратите внимание, что ответ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать и с типом int.

В первом примере выгодно купить один килограмм в понедельник за 5 рублей, получить еще один килограм в подарок и купить килограмм во вторник за 4 рубля. Купить три килограмма дешевле не получится.

Во втором примере выгодно купить три килограмма в понедельник и получить один килограмм в подарок.

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

В четвертом примере выгодно купить шесть килограммов в понедельник, получить по акции три килограмма и купить еще один килограмм во вторник.

ID 53842. Кубооктаэдр

Возьмем кубик и приклеим к его граням еще по такому же кубику. В результате получим фигуру, представленную на втором рисунке. К свободным граням полученной фигуры, приклеим еще кубики. На рисунке представлены "кубооктаэдры" степеней 0, 1, 2.

Кубооктаэдром степени N назовем фигуру, полученную в результате N-го доклеивания кубиков. Составить программу, подсчитывающую, количество кубиков для кубооктаэдра N-й степени.

Входные данные
Содержит единственное число - степень кубооктаэдра 0 <= N <= 100000

Выходные данные
Вывести одно число - количество кубиков для кубооктаэдра степени N.

ID 55078. Забор

Том Сойер получил важное задание по покраске забора. Забор состоит из n досок. Он когда-то был покрашен, однако с некоторых участков забора краска облупилась. Эти доски Тому и необходимо покрасить. Так как забор большой, пришлось подвезти к забору целую цистерну с краской. Цистерна была помещена у края забора и не может перемещаться. У Тома есть ведерко, набрав краски в которое, Том может покрасить k
 досок забора. При этом Том может в любой момент вернуться за краской к цистерне.

Изначально Том находится у цистерны. Соседние доски находятся на расстоянии 1 фута друг от друга, цистерна находится на расстоянии 1 фута от первой доски. По окончании работы Том должен положить кисточку и ведерко на свою исходную позицию рядом с цистерной.

Требуется выяснить, какое минимальное расстояние Тому необходимо пройти, чтобы покрасить забор.

Входные данные
Первая строка содержит количество досок в заборе n (1 ≤ n ≤ 10⁹) и вместимость ведерка k (1 ≤ k ≤ 100). Во второй строке содержится количество неокрашенных отрезков забора m (1 ≤ m ≤ 50).
Далее следуют m строк, в каждой из которых описан один неокрашенный отрезок. Отрезок описывается своей левой границей li и правой границей ri (1 ≤ l_i ≤ r_i ≤ n). Такое описание означает, что не покрашены l_i-я, (l_i+1)-я, …, (r_i–1)-я, r_i-я доски забора (доски нумеруются от 1 до n). Гарантируется, что неокрашенные отрезки, заданные во входном файле, не пересекаются.

Выходные данные
Выведите одно число — минимальное расстояние в футах, которое необходимо пройти Тому для выполнения своего ответственного задания.

ID 55508. Праздники

Парламент некоторой страны принял новый закон о праздничных днях. Согласно этому закону первые K дней года, а также 23 февраля (День олимпиады по информатике) и 8 марта объявляются праздничными, а все остальные праздники отменяются. При этом все выходные (суббота и воскресенье), попавшие на праздничные дни, переносятся на следующие за этими праздниками рабочие дни.

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

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

Входные данные
На вход подается единственное число K (1≤K≤50).

Выходные данные
Требуется вывести единственное число — наибольшее количество нерабочих дней, идущих подряд.

ID 58622. Печенье Муми-мамы

Мумми-мама решила испечь печенье к празднику. Она печет по B печений за один раз, и печёт их в следующие моменты времени: A минут, 2A минут, 3A минут и каждое последующее число, кратное A минутам после начала выпечки. Определите, сколько печений будет испечено Мумми-мамой к празднику, который наступит через T+0,5 после начала выпечки.

Формат входных данных
Программа получает на вход одну строку, содержащую три числа A, B и T.  1 <= A, B, T <= 20, A <= T. Все числа целые положительные.

Формат выходных данных
Выведите одно число - ответ на задачу.

ID 59851. Интересные числа

Будем назвать натуральное число интересным, если в его десятичной записи первая цифра совпадает с последней.

Дано число \(n\). Найдите количество интересных чисел, не превышающих \(n\).

Формат входных данных
На ввод подается целое число \(n\) (\(1 \le n \le 10^{18}\)).

Обратите внимание, что для считывания этого числа вам может понадобиться 64-битный тип данных (<<long long>> в C++, <<long>> в Java, <<int64>> в Паскале).

Формат выходных данных
Выведите одно целое число — количество интересных натуральных чисел, не превышающих \(n\).

ID 60137. Кузнечик 2D

В левом-нижнем углу квадратной клетчатой доски размером \(n\times m\) стоит \(k\)-кузнечик. За один ход \(k\)-кузнечик перемещается по доске вправо, вверх или вправо-вверх по диагонали не более чем на \(k\) клеток.

Необходимо передвинуть \(k\)-кузнечика в правый верхний угол доски в клетку \((n, m)\). За какое минимальное число ходов можно передвинуть \(k\)-кузнечика из клетки \((1, 1)\) в клетку \((n, m)\)?

Формат входных данных
В первой строке заданы три целых числа \(n\), \(m\) и \(k\) — размеры сторон доски и максимальное число клеток, на которое может ходить \(k\)-кузнечик, соответственно (\(1 \le n, m, k \le 10^9\)).

Формат выходных данных
Выведите одно число — минимальное число ходов, необходимое, чтобы передвинуть \(k\)-кузнечика из клетки \((1, 1)\) в клетку \((n, m)\).

ID 50861. Экзамен

В самом лучшем университете России есть специальный предмет, который называется <<Теория Лени>>. Вы очень любите этот предмет и стараетесь постоянно использовать то, чему вас там научили.

Но, как и везде, на нём есть устный экзамен. Всего есть \(n\) билетов, из которых вы выучили ровно \(a\) (ваша лень не позволяет вам выучить больше).

Экзамен проходит в стандартном формате: есть стопка с билетами, каждый билет встречается в ней ровно один раз, и каждый студент случайно выбирает себе один билет. При этом, когда студент достал билет, то он забирает его себе и не возвращает обратно в стопку.

Вы знаете, что до вас отвечали уже \(b\) человек, а это значит, что стопка содержит уже на \(b\) билетов меньше. Так как вас интересует не только <<Теория Лени>>, но и математика (и даже чуть-чуть информатика!), вы хотите узнать, какое минимальное и максимальное количество билетов из оставшихся вы можете знать.

Формат входных данных
Первая строка содержит одно целое число \(n\) (\(1 \leq n \leq 10^9\)) — количество билетов на экзамене.

Вторая строка содержит одно целое число \(a\) (\(1 \leq a \leq n\)) — количество билетов, которые вы выучили.

Третья строка содержит одно целое число \(b\) (\(0 \leq b < n\)) — количество людей, которые уже взяли свой билет до вас.

Формат выходных данных
Вывод вашей программы должен состоять из двух строк.

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

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

В первом примере давайте считать, что вы знаете билеты с номерами \(1, 2, 3, 4\). Тогда, если люди до вас вытянули билеты с номерами \(1, 2, 3\), то остался только \(1\) билет, который вы знаете. А если люди до вас вытянули билеты с номерами \(4, 5, 6\), то вы знаете \(3\) билета из оставшихся.

ID 50863. Урок физкультуры

В известной школе прошёл урок физкультуры. Как полагается, всех построили в шеренгу и попросили рассчитаться на <<первый–\(k\)-й>>.

Как известно, расчёт на <<первый–\(k\)-й>> происходит следующим образом: первые \(k\) человек имеют номера \(1, 2, 3, \ldots, k\), следующие \(k - 1\) человек имеют номера \(k - 1, k - 2, \ldots, 1\), следующие \(k - 1\) человек имеют номера \(2, 3, \ldots, k\) и т.д. Таким образом, расчёт повторяется через каждые \(2k - 2\) позиции. Примеры расчёта приведены в разделе <<Замечание>>.

Мальчик Вася постоянно всё забывает. Например, он забыл позицию, которую занимал в шеренге. Но он помнит число \(k\), описанное выше, номер, который он получил при расчёте, а также, что его позиция в шеренге была не больше \(n\). Другими словами, если Вася стоял на позиции \(y\) в шеренге, то \(y \leq n\). Помогите Васе понять, сколько есть различных позиций в ряду, где он мог стоять.

Формат входных данных
Первая строка содержит одно целое число \(k\) (\(2 \leq k \leq 10^9\)) — характеристика расчёта, описанная в условии.

Вторая строка содержит одно целое число \(x\) (\(1 \leq x \leq k\)) — номер, который Вася получил при расчёте.

Третья строка содержит одно целое число \(n\) (\(x \leq n \leq 10^9\)) — верхнее ограничение на позицию Васи.

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

Замечание

В первом примере подходят позиции равные \(2, 4, 6, 8, 10\).

Во втором примере подходят позиции равные \(2, 4, 6, 8, 10\).

В третьем примере подходят позиции равные \(3\) и \(7\).

Пример расчёта для \(k = 2\), \(k = 3\) и \(k = 5\):

ID 50862. Разрез прямоугольника

У Пети есть прямоугольник размера \(a \times b\) с целыми сторонами, хотя бы одна из которых больше \(1\). Он пробует разрезать этот прямоугольник на два прямоугольника с целыми сторонами, сделав разрез, параллельный какой-то из сторон исходного прямоугольника. Затем Петя пытается из двух получившихся прямоугольников сложить какой-то отличный от исходного прямоугольник, при этом он может как угодно поворачивать и двигать эти два прямоугольника. Если у него получается это сделать, то он называет прямоугольник \(a \times b\) интересным.

Обратите внимание, что если два прямоугольника отличаются поворотом на \(90^{\circ}\), то они считаются одинаковыми. Например, прямоугольники \(6 \times 4\) и \(4 \times 6\) считаются одинаковыми.

Таким образом, прямоугольник \(2 \times 6\) является интересным, потому что его можно разрезать на два прямоугольника \(2 \times 3\), после чего из этих двух прямоугольников сложить прямоугольник \(4 \times 3\), который отличается от прямоугольника \(2 \times 6\).

При этом прямоугольник \(2 \times 1\) не является интересным, потому что его можно разрезать только на два прямоугольника \(1 \times 1\), а из них можно сложить только прямоугольники \(1 \times 2\) и \(2 \times 1\), которые считаются одинаковыми с исходным.

Также у Пети есть некоторое целое число \(n\). Он хочет узнать, сколько существует различных интересных прямоугольников со сторонами, которые являются целыми числами, не превосходящими \(n\). Помогите ему это сделать.

Формат входных данных
Первая и единственная строка содержит одно целое число \(n\) (\(2 \le n \le 2 \cdot 10^9\)) — ограничение на длину сторон прямоугольника.

Формат выходных данных
Выведите одно целое число — количество различных интересных прямоугольников с длинами сторон, не превышающими \(n\).

Обратите внимание, что ответ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать.

Замечание

В первом примере только прямоугольник \(2 \times 2\) является интересным: его можно разрезать на два прямоугольника \(1 \times 2\), а из них можно сложить прямоугольник \(1 \times 4\). Обратите внимание, что прямоугольник \(1 \times 1\) не является интересным, потому что хотя бы одна сторона должна быть больше \(1\).

Во втором примере прямоугольники \(2 \times 2\) и \(2 \times 3\) являются интересными. Прямоугольник \(2 \times 3\) можно разрезать на два прямоугольника \(1 \times 3\), а из них можно сложить прямоугольник \(1 \times 6\). Прямоугольник \(3 \times 3\) не является интересным, потому что его можно разрезать только на два прямоугольника \(1 \times 3\) и \(2 \times 3\), но из них можно сложить только прямоугольник \(3 \times 3\). Обратите внимание, что прямоугольники \(2 \times 3\) и \(3 \times 2\) считаются одинаковыми, поэтому в ответе их нужно учесть только один раз.

ID 60228. Суммы модулей

Для последовательности целых чисел \(a_1, a_2, \ldots, a_n\) и целого числа \(x\) обозначим через \(f(a, x)\) количество таких целых \(i\) от \(1\) до \(n\), что \(a_i \le x\).

Для пары последовательностей целых чисел \(a_1, a_2, \ldots, a_n\) и \(b_1, b_2, \ldots, b_n\) обозначим через \(g(a, b, c)\) сумму значений \(|f(a, x)-f(b, x)|\) по всем целым \(x\), лежащим в отрезке \([0, c]\). Более формально, \(g(a, b, c) = \sum_{x=0}^c |f(a, x)-f(b, x)|\).

Вам даны два целых числа \(n\) и \(c\), а также две последовательности целых чисел \(a_1, a_2, \ldots, a_n\) и \(b_1, b_2, \ldots, b_n\), все элементы которых лежат в отрезке \([-1, c]\). Известно, что ни в \(a\), ни в \(b\) нет двух подряд идущих элементов, равных \(-1\).

Скажем, что пара последовательностей целых чисел \(a_1', a_2', \ldots, a_n'\) и \(b_1', b_2', \ldots, b_n'\), все элементы которых лежат в отрезке \([0, c]\), соответствует шаблону \((a, b)\), если выполняются следующие условия:

• Для всех \(i\) (\(1 \le i \le n\)), таких, что \(a_i \ne -1\), выполняется \(a_i'=a_i\).

• Для всех \(i\) (\(1 \le i \le n\)), таких, что \(b_i \ne -1\), выполняется \(b_i'=b_i\).

• Для всех \(i\) (\(1 \le i \le n-1\)) выполняется \(a_i' \le a_{i+1}'\).

• Для всех \(i\) (\(1 \le i \le n-1\)) выполняется \(b_i' \le b_{i+1}'\).

Обозначим через \(h(a, b, c)\) сумму значений \(g(a', b', c)\) по всем парам последовательностей \((a', b')\), соответствующих шаблону \((a, b)\). Вы должны посчитать \(h(a, b, c)\). Также вы должны обработать \(q\) запросов изменения последовательностей \(a\) и \(b\) и посчитать \(h(a, b, c)\) после каждого изменения. Обратите внимание, что ни в \(a\), ни в \(b\) нет двух подряд идущих элементов, равных \(-1\), ни до всех запросов, ни после какого-либо запроса.

Формат входных данных
Первая строка содержит три целых числа \(n\), \(c\) и \(q\) (\(1 \le n \le 100\,000\), \(0 \le c \le 10^9\), \(0 \le q \le 100\,000\)) — длина последовательностей \(a\) и \(b\), ограничение на значения элементов \(a\) и \(b\) и количество запросов, соответственно.

Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(-1 \le a_i \le c\)) — последовательность \(a\).

Третья строка содержит \(n\) целых чисел \(b_1, b_2, \ldots, b_n\) (\(-1 \le b_i \le c\)) — последовательность \(b\).

В следующих \(q\) строках заданы запросы изменения. Каждый запрос задается тройкой целых чисел \(t\), \(p\), \(x\) (\(1 \le t \le 2\), \(1 \le p \le n\), \(-1 \le x \le c\)). Если \(t=1\), то данный запрос меняет \(a_p\) на \(x\). Если \(t=2\), то данный запрос меняет \(b_p\) на \(x\).

Гарантируется, что до всех изменений и после каждого изменения ни в \(a\), ни в \(b\) нет двух подряд идущих элементов, равных \(-1\).

Формат выходных данных
Выведите \((q+1)\) строку. В \((i+1)\)-й строке (\(0 \le i \le q\)) выведите одно целое число — значение \(h(a, b, c)\) по модулю \(10^9+7\) после применения первых \(i\) запросов изменения.

Примечание
Рассмотрим первый тест из примера. В нем \(n=3\), \(c=4\), \(q=3\). До всех запросов \(a=[-1, 1, 3]\), \(b=[1, -1, 2]\). Шаблону \((a, b)\) соответствуют следующие пары последовательностей:

• \(a'=[0, 1, 3], b'=[1, 1, 2]\), \(g(a, b, 4)=2\).

• \(a'=[0, 1, 3], b'=[1, 2, 2]\), \(g(a, b, 4)=3\).

• \(a'=[1, 1, 3], b'=[1, 1, 2]\), \(g(a, b, 4)=1\).

• \(a'=[1, 1, 3], b'=[1, 2, 2]\), \(g(a, b, 4)=2\).

Таким образом, ответ на задачу до всех запросов равен \(h(a, b, 4)=2+3+1+2=8\).

В первом запросе \(t=1\), \(p=1\), \(x=2\). Этот запрос меняет \(a_1\) с \(-1\) на \(2\). Таким образом, после этого запроса \(a=[2, 1, 3]\), \(b=[1, -1, 2]\). В последовательности \(a\) нет \(-1\), поэтому в любой паре последовательностей \((a', b')\), соответствующей шаблону \((a, b)\), последовательность \(a'\) должна совпадать с \(a\). В последовательности \(a\) не выполняется условие \(a_1 \le a_2\), поэтому не существует ни одной пары последовательностей, соответствующей шаблону, а тогда \(h(a, b, 4)=0\) после первого запроса.

ID 60586. Качели

Трое друзей — Аня, Боря и Саш — пришли на детскую площадку, чтобы покачаться на качеляхбалансире. Качели представляют собой длинную балку, закреплённую в центре, на которую дети садятся с разных концов.

Массы детей равны A, B и C кг. Чтобы держать баланс на качелях, разница масс на двух концах качелей должна быть не более D кг. Друзьям повезло: рядом с площадкой оказалась груда достаточно тяжёлых камней. Один из детей может взять с собой любой камень, чтобы сделать разность масс на концах качелей допустимой. Помогите друзьям определить минимальную массу камня, благодаря которому они смогут покачаться на качелях.

Формат входных данных
Программа получает на вход три числа A, B, C, записанных в отдельных строках, — массы друзей. В четвёртой строке записано число D — наибольшая допустимая разница масс на концах качелей. Все числа — целые, положительные и не превосходящие 10⁹ .

Формат выходных данных
Программа должна вывести одно целое число — минимальную необходимую массу камня, которую нужно добавить на одну из сторон качелей, чтобы друзья смогли покачаться на них, сев оптимально. Если камень им не понадобится, программа должна вывести число 0. 

Замечание
В первом примере Аня и Саша сядут на одну сторону, их суммарная масса будет равна 65 кг. На другую сторону сядет Боря, взяв 15-килограммовый камень, тогда масса Бори с камнем составит 55 кг. Разница весов на концах качелей примет значение 10 кг. Во втором примере Аня и Боря сядут на одну сторону (50 кг), Саша — на другую сторону (45 кг). Разница весов будет равна 5 кг, поэтому камень не понадобится.