Пашка очень любит играть в шахматы. К сожалению, компьютерные программы легко обыгрывают даже чемпионов мира, поэтому мальчик решил разнообразить правила игры.
По мнению юного шахматиста, пешка — слишком слабая фигура. Для её усиления Пашка разрешает ей бить по диагонали на любое количество клеток (но, по-прежнему, только вперёд). Новую фигуру мальчик называет пушкой и старательно исследует её свойства.
Помогите мальчику определить, сколько белых пушек достаточно, чтобы контролировать все поля шахматной доски размером n × n. Других фигур на доске нет. Считайте, что пушка контролирует и ту клетку, на которой стоит.
Формат входных данных
Единственная строка входных данных содержит натуральное число n.
Формат выходных данных
Выведите одно натуральное число — ответ на вопрос задачи.
Ограничения
1 ≤ n ≤ 109
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n ≤ 8, получат не менее 35 баллов.
Решения, верно работающие при n ≤ 105, получат не менее 70 баллов.
Пояснение к примеру
Смотри рисунок. Пушки на нижней горизонтали бьют все поля кроме b3. Добавим туда четвёртую пушку. Меньшим количеством фигур обойтись нельзя.
Прямоугольник размером a × b разбили на единичные квадраты и записали в каждый из них числа от 1 до a × b по порядку (слева направо, сверху вниз). Два квадрата считаются соседними, если у них есть общая сторона. Существуют ли два соседних квадрата, сумма чисел в которых равна n?
Формат входных данных
Три строки входных данных содержат натуральные числа a, b и n.
Обратите внимание, что значения переменных в этой задаче могут превышать возможные значения 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Формат выходных данных
Выведите Yes или No — ответ на вопрос задачи.
Ограничения
1 ≤ a, b ≤ 109
1 ≤ n ≤ 1018
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при a = 1, получат не менее 20 баллов.
Решения, верно работающие при b = 1, получат не менее 20 баллов.
Решения, верно работающие при a, b ≤ 100, n ≤ a × b, получат не менее 40 баллов.
Пояснение к примеру
Смотри рисунок. Требуемая сумма не набирается нигде:
Говорят, что у Бабы Яги есть волшебные механические часы без стрелок, висящие напротив печки. Поскольку время в Зачарованном лесу идет не так, как на остальной земле, циферблат часов разбит на n секторов, обозначенных числами от 1 до n, причём дважды: внутри циферблата и снаружи.
И если повернуть циферблат часов вокруг оси таким образом, чтобы сумма модулей разности соответствующих чисел стала равна s, то лишится Баба Яга всей своей магической силы. Да вот только как это сделать?
Формат входных данных
Две строки входных данных содержат натуральные числа n и s. Гарантируется, что для указанных входных данных ответ существует.
Обратите внимание, что значения переменных в этой задаче могут превышать возможные значения 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Формат выходных данных
Выведите число, которое нужно установить напротив единицы на внешнем кольце чисел. Если есть несколько подходящих ответов, выведите наименьший.
Ограничения
2 ≤ n ≤ 109
2 ≤ s ≤ 1018
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n ≤ 100, получат не менее 40 баллов.
Пояснение к примеру
В примере дано n = 5 и s = 12. При начальном положении часов нужная сумма равна |1 − 1| + |2 − 2| + |3 − 3| + |4 − 4| + |5 − 5| = 0.
Повернём циферблат на одно деление. Сумма стала равна |1 − 2| + |2 − 3| + |3 − 4| + |4 − 5| + |5 − 1| = 8.
Повернём циферблат ещё на одно деление. Сумма стала равна |1 − 3| + |2 − 4| + |3 − 5| + |4 − 1| + |5 − 2| = 12. Нужная сумма набрана, напротив единицы на внешнем кольце установлена тройка на внутреннем кольце.
Примечание: нужной суммы можно добиться и при установке четвёрки, однако тройка меньше.
На полках сети магазинов настольных игр "Черное и Белое" каждый месяц появляется новая игра. Дизайном миплов (фигурки в виде животных или людей, которые используют как фишки) занимается Тимофей, основной принцип которого — чем реже встречается мипл, там выше он должен быть. По описанию набора фигурок определите их суммарную высоту.
В целях экономии расходного материала, высоты миплов, отличающиеся по количеству от предыдущего, увеличиваются на 1. Высота самого часто встречающегося мипла должна быть равна 1.
Формат входных данных
Первая строка входных данных содержит натуральное число n — количество различных типов миплов. В следующих n строках расположены натуральные числа xi — количество фигурок i-го типа в наборе для игры, отсортированные по неубыванию.
Формат выходных данных
Выведите одно натуральное число — ответ на вопрос задачи.
Ограничения
1 ≤ n ≤ 105
1 ≤ xi ≤ 100
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n ≤ 2, получат не менее 20 баллов.
Решения, верно работающие на тестах, где все xi различны, получат не менее 20 баллов.
Пояснение к примерам
В первом примере в наборе для игры используются 24 одинаковых фигурки (как в классических шашках, их цвет в данной задаче не важен). Установив высоту одной шашки равной 1, получим их суммарную высоту 24.
Во втором примере в наборе для игры используются 6 различных типов фигурок (как в шахматах). Для 16 самых часто встречающихся фигур (пешек) установим высоту 1, для трёх следующих типов, встречающихся по 4 раза (кони, слоны и ладьи), установим высоту 2, для двух следующих типов, встречающихся по 2 раза (короли и ферзи), установим высоту 3. Всего получается 16 × 1 + (4 + 4 + 4) × 2 + (2 + 2) × 3 = 16 + 24 + 12 = 52.
Карлсон обожает мясные тефтели. А ещё он обожает собирать башни из кубиков. Для каждой построенной Карлсоном башни Малыш считает число более низких башен, а потом складывает получившиеся величины. Карлсон получит от мамы Малыша столько тефтелек, чему будет равна эта сумма. Помогите Карлсону определить, какое наибольшее количество тефтелей он сможет получить, если у Малыша n кубиков?
Формат входных данных
Единственная строка входных данных содержит натуральное число n.
Обратите внимание, что значения переменных в этой задаче могут превышать возможные значения 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Формат выходных данных
Выведите одно неотрицательное целое число — ответ на вопрос задачи.
Ограничения
1 ≤ n ≤ 109
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n ≤ 100, получат не менее 40 баллов.
Пояснение к примеру
В примере дано n = 4. Переберем все возможные способы построения башен.
1) Одна башня высотой 4. Нет башен ниже её, сумма равна 0.
2) Две башни высотой 3 и 1. Одна башня ниже одной другой, сумма 1.
3) Две башни высотой 2 и 2. Все башни равной высоты, сумма 0.
4) Три башни высотой 2, 1 и 1. Для башни высоты 2 есть две башни ниже её, сумма 2.
5) Четыре башни высотой 1. Все башни равной высоты, сумма 0.
