Автор: | Антон Карабанов | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 64 Мб | |
Выходной файл: | Стандартный выход | |||
Максимальный балл: | 100 |
Скоро Новый Год! А это значит, что самое время украшать ёлку красивыми, разноцветными и яркими игрушками.
Ёлочка Тимофея имеет свою красоту, равную количеству ветвей с одной стороны ствола и (так уж совпало) длине самой нижней ветви. Каждая следующая верхняя ветка на одну клетку короче предыдущей. Между ветвями, а также под самой нижней и над самой верхней ветвями находится ствол дерева шириной ровно в одну клетку. На рисунке вы видите ёлки красотой от 0 до 5 включительно. Каждая игрушка может располагается на одной из клеток, принадлежащей ёлке.
Тимофей хочет разместить на своей ёлке как можно больше игрушек. При этом, чтобы не портить впечатление, он решил, что игрушки не могут занимать две соседние клетки (но могут касаться углами). Помогите Тимофею узнать наибольшее количество игрушек, которыми ему удастся украсить ёлку красотой n.
В единственной строке записано одно неотрицательное целое число n — красота елки.
Выведете одно натуральное число — ответ на задачу.
0 ≤ n ≤ 109
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Подзадача 1: n ≤ 105, баллы: 30.
Подзадача 2: нет дополнительных ограничений, баллы: 70.
В примере дана ёлка красоты 5. Пример украшения — на рисунке.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|