Скоро Новый Год! А это значит, что на носу конец второй четверти и Тимофею самое время взяться за исправление отметок по рисованию. На сегодняшнем уроке весь класс рисует зимний лес. К сожалению, с передачей художественных образов изобразительными методами дела у Тимофея обстоят из рук вон плохо. Но хоть что-то нарисовать нужно, поэтому Тимофей рисует ёлочки по клеточкам.
Каждая елочка имеет свою красоту, равную количеству ветвей с одной стороны ствола и (так уж совпало) длине самой нижней ветви. Каждая следующая верхняя ветка на одну клетку короче предыдущей. Между ветвями, а также под самой нижней и над самой верхней ветвями находится ствол дерева шириной ровно в одну клетку. На рисунке вы видите ёлки кисти Тимофея красотой от 0 до 5 включительно.
Поскольку с математическими формулами Тимофей дружит гораздо сильнее, чем с акварельными красками, его заинтересовал вопрос, какой периметр у клетчатой ёлки определенной красоты? Тимофей без труда решил эту задачу. А вы сможете?
Формат входных данных
В единственной строке записано одно неотрицательное целое число n - красота ёлки.
Формат выходных данных
Выведете одно натуральное число - периметр ёлки красоты n.
Ограничения
0 ≤ n ≤ 109
Система оценки и описание подзадач
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Подзадача 1: 0 ≤ n ≤ 105, баллы: 30.
Подзадача 2: нет дополнительных ограничений, баллы: 70.
Ох уж эти уроки математики... Сегодня учитель Дмитрий Анатольевич развлекался игрой "Сумма кубов". Он записывал на доске два натуральных числа a и b и требовал, чтобы класс ответил на вопрос, какая цифра будет последней у суммы кубов всех чисел от a до b включительно. Пока никто не пострадал от гнева Дмитрия Анатольевича, напишите программу, находящую ответ на этот вопрос.
Формат входных данных
В единственной строке входного файла через пробел записаны два натуральных числа: a и b.
Формат выходных данных
Выведите одну десятичную цифру - ответ на задачу.
Ограничения
1 ≤ a ≤ b ≤ 1018
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснения к примерам
В первом примере нужно найти сумму кубов чисел от 3 до 5 включительно. Вычислим её: 33 + 43 + 53 = 27 + 64 + 125 = 216. Последняя цифра 6.
Тимофей всерьез занялся марафонским бегом. Он бережно относится к своему здоровью, тщательно подбирает рацион питания и тренируется, тренируется, тренируется...
Соревнования по марафону проходят на стадионе, всем участникам необходимо пробежать ровно n кругов. Тимофей после многомесячных тренировок точно узнал свои возможности: первый круг он пробежит за t минут, затем начнет сказываться усталость от уже преодолённой дистанции, поэтому второй круг он пробежит медленнее - за t + a минут, третий - за t + 2 ⋅ a, и т.д., то есть m-ый круг Тимофей пробежит за t + (m − 1) ⋅ a минут. Однако, как только время, затраченное на очередной круг станет строго больше v, у марафонца откроется второе дыхание и все остальные круги он будет бежать с постоянным временем v.
Определите, сколько минут потребуется Тимофею для того, чтобы пробежать n кругов?
Формат входных данных
В единственной строке через пробел записаны четыре неотрицательных целых числа: n, t, a и v.
Формат выходных данных
Выведете одно натуральное число - время бега в минутах. Гарантируется, что ответ не превысит 1018.
Ограничения
1 ≤ n ≤ 1012
1 ≤ t ≤ 100
0 ≤ a ≤ 100
1 ≤ v ≤ 1018
Система оценки и описание подзадач
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Подзадача 1: 0 ≤ n ≤ 105, баллы: 30.
Подзадача 2: нет дополнительных ограничений, баллы: 70.
Пояснения к примерам
В первом примере Тимофею нужно пробежать 8 кругов. Первый круг он пробежит за 10 минут. Второй - за 12, третий - за 14, четвертый - за 16. После четвертого круга время, затрачиваемое на круг, стало больше 15, поэтому пятый круг спортсмен пробежит за 15 минут, на шестой (и все оставшиеся) круги марафонец будет тратить те же 15 минут.
Недавно Тимофею на занятии математического кружка рассказали про многоугольные числа. Напомним, что это числа, связанные с геометрическими построениями определённого типа и соответствующие количеству точек, расположенных в форме многоугольников. В общем случае многоугольное n-е число изображают в виде соответствующего правильного многоугольника, на стороне которого расположено n точек. На рисунке внизу вы видите примеры построения последовательностей треугольных, квадратных и пятиугольных чисел.
Тимофей заинтересовался вопросом - как найти n-е по порядку k-угольное число?
Формат входных данных
Единственная строка входного файла содержит два натуральных числа n и k, записанных через пробел.
Формат выходных данных
В единственной строке выходного файла выведите одно натуральное число - n-е по порядку k-угольное число. Гарантируется, что ответ на задачу не превысит 1018.
Ограничения
1 ≤ n ≤ 109
3 ≤ k ≤ 109
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснения к примерам
В первом примере нужно найти третье квадратное число: 32 = 9.
Во втором примере нужно найти первое стоугольное число: 1.
Джек-из-Тени - самый искусный вор на тёмной стороне планеты Твилайт. Естественными врагами Джека является свет или тьма в чистом виде, которых он пытается не встречать на своём пути, так как полностью в них беспомощен.
В настоящий момент Джек находится в чистом поле, где установлено два фонаря, равномерно отбрасывающих свет. Джек хочет поскорее спрятаться от Повелителя Нетопырей. Для этого ему нужно найти место, освещенное одним (любым) источником света и не освещенное другим.
Формально: два круга заданы на плоскости координатами своих центров и радиусами. Определите количество точек плоскости с целочисленными координатами, принадлежащих ровно одному кругу из двух.
Формат входного файла
В первой строке входного файла через пробел записаны два целых числа - координаты центра первого круга и одно натуральное число - его радиус.
Во второй строке в том же формате задано положение второго круга.
Формат выходного файла
В единственной строке выходного файла запишите одно целое число - искомое количество точек.
Ограничения
− 50000 ≤ x, y ≤ 50000 - координаты центров кругов.
1 ≤ r ≤ 50000 - радиусы кругов.
Система оценки и описание подзадач
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Подзадача 1: − 100 ≤ x, y ≤ 100, 1 ≤ r ≤ 100, баллы: 40.
Несколько лет назад Тимофей (после долгих мучений) научился рисовать пятиугольную звезду. Сначала он расставлял пять точек на окружности на равном расстоянии друг от друга. После этого он соединял эти точки отрезками по часовой стрелке от первой вершины, пропуская ровно одну вершину. А сегодня на занятии кружка по математике Тимофей узнал про звездчатые многоугольники. Строятся они так: каждая вершина правильного n-многоугольника соединяется с m-ной от неё на окружности по часовой стрелке. Звезда, полученная таким образом, обозначается как {n/m} (например, пятиконечная звезда, которую рисовал Тимофей в детстве, обозначается как {5/2}). При этом точки пересечения сторон между собой не рассматриваются как вершины. Такая звезда имеет n вершин и n сторон, также как и правильный n-угольник.
Дома Тимофей выбрал число n и начал рисовать все возможные звездчатые n-угольники от {n/1} до {n/n-1}. Некоторые рисунки ему понравились больше других - в них проведенные стороны пересекались между собой и не распадались на несколько связанных групп (как например, в фигуре {6/2} проведенные стороны распадаются и образуют два треугольника). Такие звезды Тимофей называет красивыми. Теперь Тимофею хочется по заданному n узнать количество различных красивых звездчатых n-угольников.
Формат входных данных
Единственная строка входного файла содержит одно натуральное число n - количество вершин.
Формат выходных данных
Выведите одно неотрицательное целое число - количество различных красивых звездчатых многоугольников.
Ограничения
3 ≤ n ≤ 105
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примеру
В примере даны вершины правильного семиугольника. Стороны звездчатого многоугольника {7/1} не пересекаются, {7/2} и {7/3} - красивые, {7/4} совпадает с {7/3}, а {7/5} совпадает с {7/2}. Стороны звездчатого многоугольника {7/6} не пересекаются. Всего красивыми являются два варианта.
Сегодня на занятии кружка по математике Тимофей узнал о существовании фигурных чисел. Больше всего его заинтересовали треугольные и квадратные числа.
Напомним, что число называется треугольным, если количество объектов, которое оно выражает, можно расставить в виде правильного треугольника. Аналогично, если это количество можно расставить в виде квадрата, то число называется квадратным.
На рисунке вы видите начало ряда треугольных чисел (1, 3, 6, 10, ...) и ряда квадратных чисел (1, 4, 9, 16, ...).
Тимофею нравится находить закономерности. Он смог доказать, что любое квадратное число (если оно больше 1) представимо в виде суммы всего двух треугольных чисел! Для поиска более сложных закономерностей ему нужно знать количество различных способов это сделать.
Помогите Тимофею! Найдите количество способов представления данного квадратного числа в виде суммы двух треугольных. Способы, отличающиеся порядком слагаемых, считаются одинаковыми.
Формат входных данных
В единственной строке входного файла записано одно натуральное квадратное число n.
Формат выходных данных
Выведите одно натуральное число - ответ на задачу.
Ограничения
4 ≤ n ≤ 1010
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснения к примерам
Комментарий к первому примеру: существует единственный способ представить 4 в виде суммы двух треугольных чисел: 4 = 3 + 1.
Комментарий ко второму примеру: существует два способа представить 16 в виде суммы двух треугольных чисел: 16 = 10 + 6 = 15 + 1.
Комментарий к третьему примеру: существует четыре способа представить 10000 в виде суммы двух треугольных чисел: 10000 = 5050 + 4950 = 5995 + 4005 = 8515 + 1485 = 9180 + 820.
По сюжету сатирической сказки Михаила Салтыкова-Щедрина «Повесть о том, как один мужик двух генералов прокормил», два отставных генерала, выйдя на пенсию, неизвестным образом попадают на необитаемый остров. Они хотят выбраться с острова, однако не могут, поскольку даже не разбираются в сторонах света. Вскоре они решают найти мужика (то есть крестьянина), который сможет их вернуть домой. Генералы находят на острове мужика. Мужик строит для них лодку и переправляет через моря в Петербург. По прибытии в Петербург они наедаются, напиваются и едут в казначейство за деньгами. В благодарность за спасение с острова они посылают мужику рюмку водки и пятак серебра, восклицая: «Веселись, мужичина!».
Но у нас не сказка, а задача, да и генералы с тех пор слегка изменились, поэтому они будут помогать мужику строить лодку. Для её изготовления нужно n досок, каждый человек за один день способен сделать одну доску. Мужик, как архетип неутомимого народа, способен работать каждый день, а вот генералам нужен отдых, выходные и отпуск на море (хорошо, что место действия соответствует). Поэтому первый генерал работает a дней подряд, а потом b дней подряд отдыхает. Второй генерал работает c дней подряд, а потом d дней подряд отдыхает. Как скоро будет построена лодка?
Формат входных данных
Единственная строка входного файла содержит пять натуральных чисел, записанных через пробел: n - требуемое количество досок, a, b, c и d - расписание работы генералов.
Формат выходных данных
В единственной строке выведите одно натуральное число - минимальное количество дней, требуемое для постройки лодки.
Ограничения
1 ≤ n ≤ 1018.
1 ≤ a, b, c, d ≤ 1015.
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при 1 ≤ n ≤ 106, получат не менее 40 баллов.
Пояснения к примерам
В первом примере нужно изготовить 11 досок. Мужик работает каждый день, первый генерал работает один день, потом отдыхает два дня, второй генерал работает два дня, потом отдыхает три. События будут развиваться следующим образом:
В первый день мужик и оба генерала делают по одной доске каждый.
Во второй день мужик и второй генерал делают по одной доске каждый, первый генерал отдыхает. Всего готово 5 досок.
В третий день работает только мужик, оба генерала отдыхают. Всего готово 6 досок.
В четвертый день мужик и первый генерал делают по одной доске каждый, второй генерал отдыхает. Всего готово 8 досок.
В пятый день работает только мужик, оба генерала отдыхают. Всего готово 9 досок.
В шестой день мужик и второй генерал делают по одной доске каждый, первый генерал отдыхает. Всего готово 11 досок - лодка построена. Работа завершена за 6 дней.
Тимофей увлекся настольными ролевыми играми. В его речи всё чаще встречаются непонятные окружающим термины "билд", "данж", "отыгрыш", "каст с хитов" и тому подобные. Все карманные деньги Тимофей тратит на фигурки персонажей, карты подземелий и, конечно, наборы игральных костей (дайсы) без которых не обходится ни одна партия.
Дайс представляет собой многогранник, на сторонах которого записаны числа. В коллекции Тимофея собраны разнообразнейшие кубики, которые позволяют генерировать выпадение любых натуральных чисел. Для удобства Тимофей описывает каждый дайс максимальным числом, которое записано на одной из его граней. Например, дайс5 позволяет выбросить любое целое число от 1 до 5 включительно, а дайс100 - от 1 до 100.
Для сегодняшней игры с друзьями Тимофей приготовил набор из n дайсов. Во время своего хода участник игры выбрасывает все n дайсов, считает сумму выпавших очков и расходует их на перемещение персонажа, атаку им монстров, лечение, починку оружия и доспехов и прочие действия. Тимофей, как мастер игры, хочет премировать участника дополнительными очками в случае, если тот угадает количество способов получить выпавшую у него сумму очков. Для проверки правильности ответов Тимофей попросил Вас написать программу, определяющую по стартовому набору дайсов и сумме выпавших очков это количество.
Формат входных данных
В первой строке через пробел записаны два натуральных числа n и s - количество дайсов и сумма очков. Во второй строке через пробел записаны n натуральных чисел di - описание i-го дайса.
Формат выходных данных
Выведете одно неотрицательное целое число - количество способов. Предупреждение - ответ может быть очень большой.
Ограничения
1 ≤ n ≤ 100
1 ≤ s ≤ 109
2 ≤ di ≤ 100
Система оценки и описание подзадач
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Подзадача 1: n = 1, баллы: 10.
Подзадача 2: n = 2, баллы: 20.
Подзадача 3: n ≤ 12, di = 2, баллы: 20.
Подзадача 4: нет дополнительных ограничений, баллы: 50.
Пояснения к примерам
Комментарий к первому примеру: существует единственный способ выбросить 1 с помощью одного стандартного шестигранного игрального кубика.
Комментарий ко второму примеру: у Тимофея два дайса: первый позволяет выбрасывать числа от 1 до 2, второй - от 1 до 6. Число 4 можно набрать двумя способами: выбросить 1 на первом дайсе и 3 на втором или выбросить 2 на обоих дайсах.
Комментарий к третьему примеру: сумму 4 с помощью пяти дайсов получить невозможно.
