Скоро Новый Год! А это значит, что самое время украшать ёлку красивыми, разноцветными и яркими игрушками.
Ёлочка Тимофея имеет свою красоту, равную количеству ветвей с одной стороны ствола и (так уж совпало) длине самой нижней ветви. Каждая следующая верхняя ветка на одну клетку короче предыдущей. Между ветвями, а также под самой нижней и над самой верхней ветвями находится ствол дерева шириной ровно в одну клетку. На рисунке вы видите ёлки красотой от 0 до 5 включительно. Каждая игрушка может располагается на одной из клеток, принадлежащей ёлке.
Тимофей хочет разместить на своей ёлке как можно больше игрушек. При этом, чтобы не портить впечатление, он решил, что игрушки не могут занимать две соседние клетки (но могут касаться углами). Помогите Тимофею узнать наибольшее количество игрушек, которыми ему удастся украсить ёлку красотой n.
Формат входных данных
В единственной строке записано одно неотрицательное целое число n — красота елки.
Формат выходных данных
Выведете одно натуральное число — ответ на задачу.
Ограничения
0 ≤ n ≤ 109
Система оценки и описание подзадач
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Подзадача 1: n ≤ 105, баллы: 30.
Подзадача 2: нет дополнительных ограничений, баллы: 70.
Пояснение к примеру
В примере дана ёлка красоты 5. Пример украшения — на рисунке.
Девочка Вика любит в новогоднюю ночь зажигать свечи. Вот и в этот раз она зажгла n свечей. Каждая свеча характеризуется двумя параметрами: высотой (в сантиметрах) и скоростью сгорания (в сантиметрах в минуту). Помогите Вике определить, через какое целое число минут погаснет не менее половины всех зажженных свечек?
Формат входных данных
Первая строка входного файла содержит натуральное число n — количество зажженных свечек. Во второй строке через пробел расположены n целых чисел xi — высота i-й свечки. В третьей строке через пробел расположены n целых чисел yi — скорость сгорания i-й свечки.
Формат выходных данных
Выведите одно натуральное число — количество минут, необходимые для того, чтобы сгорело и погасло не менее половины всех свечек.
Ограничения
1 ≤ n ≤ 105
1 ≤ xi, yi ≤ 109
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n = 1, получат не менее 10 баллов.
Решения, верно работающие при n = 2, получат не менее 20 баллов.
Пояснение к примеру
В примере дано три свечи высотой 20, 6 и 12 сантиметров. Первая свеча сгорает со скоростью 1 см/мин, следовательно она будет гореть ровно 20 минут. Вторая свеча сгорает со скоростью 5 см/мин, следовательно она будет гореть 65 = 115 минут. Третья свеча сгорает со скоростью 7 см/мин, следовательно она будет гореть 127 = 157 минут. Таким образом уже через две минуты погаснут две свечи из трех.
Антону нужно перевезти из одного города в другой партию из n новогодних хлопушек. В соответствии с правилами транспортной безопасности ГОСТ-202021, перевозить их можно только партиями в кубических коробках (куда поместится k × k × k хлопушек, то есть 1, 8, 27, 64, ... ) или в почти кубических коробках (куда поместится k × k × (k − 1) хлопушек, то есть 4, 18, 48, ... ). Коробки должны быть заполнены полностью.
У Антона есть по одной коробке любого разрешенного вида. Помогите ему определить минимальное количество коробок, которое понадобится при перевозке.
Формат входных данных
Единственная строка входного файла содержит натуральное число n — количество хлопушек.
Формат выходных данных
Выведите одно натуральное число — ответ на задачу. Если перевезти все хлопушки невозможно — выведите число -1.
Ограничения
1 ≤ n ≤ 105
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n ≤ 100, получат не менее 40 баллов.
Пояснение к примерам
В первом примере Антону требуется перевезти 58 хлопушек. Он может разложить их по коробкам таким образом: 27 + 18 + 8 + 4 + 1. Меньшим числом коробок обойтись нельзя.
Во втором примере Антону не удастся разложить 43 хлопушки по коробкам.
Дед Мороз подарил веселым зверюшкам r красных, g зеленых и b синих конфет, и они стали ещё веселее! Чтобы их успокоить, Снегурочка предложила определить количество способов разложить все конфеты в одну линию так, чтобы конфеты одного цвета не лежали рядом.
Формат входных данных
Единственная строка входного файла содержит три натуральных числа r, g и b.
Формат выходных данных
Выведите одно натуральное число — ответ на задачу. Гарантируется, что он не превысит 1012.
Тимофей склеил из картона домик, но разыгравшиеся коты его перевернули. Определите координаты самой высокой точки перевернутого дома.
Домик состоит из двух частей — квадрата с диагональю a и равнобедренного прямоугольного треугольника с катетом b. В настоящее время домик лежит так, как указано на рисунке. Тимофей старался и домик получился ровным, поэтому получившаяся конструкция симметрична относительно прямой y = x.
Формат входных данных
Первая строка входного файла содержит натуральное число a, вторая — натуральное число b.
Формат выходных данных
Выведите через пробел координаты искомой точки. Гарантируется, что входные данные таковы, что такая точка одна и имеет целочисленные координаты.
Наступает Новый год! Повсюду слышатся поздравления, звон курантов и хлопки петард. А Тимофей вынужден до утра дежурить в НИИ изучения натуральных чисел. Чтобы не скучать, Тимофей выписал на длинную ленту все натуральные числа от 1 до n включительно без пробелов (получилась строка 123456789101112131415...) и задумался, а сколько раз в этой строке встретится подстрока 2021?
Формат входных данных
Единственная строка входного файла содержит одно натуральное число n.
Формат выходных данных
Выведите неотрицательное целое число — ответ на задачу.
Ограничения
1 ≤ n ≤ 106
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснения к примерам
В первом примере n = 24. Конец строки Тимофея будет выглядеть так: ...192021222324.
Во втором примере n = 2021. Помимо случая, рассмотренного выше, искомая подстрока возникает на стыке чисел 1202 и 1203, а также в самом числе 2021.
