АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1851. Треугольник Паскаля

Ограничение времени: 1 сек.
Ограничение памяти:262144 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Наверное, вы знакомы с треугольником Паскаля. Напомним, что треугольник Паскаля – бесконечная таблица биномиальных коэффициентов, имеющая треугольную форму. В этом треугольнике на вершине и по бокам стоят единицы. Каждое другое число равно сумме двух расположенных над ним чисел.

Математик Иван предложил программисту Тимофею взять треугольник Паскаля с количеством строк N и заменить в нём все числа на их остатки от деления на 3. Теперь Иван и Тимофей хотят посчитать количество ненулевых элементов в получившемся треугольнике. Помогите им это сделать.

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

В единственной строке ввода дано натуральное число 1 ≤ N ≤ 109.

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

В ответе напечатайте одно целое число – количество ненулевых элементов.

Примеры

Входные данные
2
Выходные данные
3
Входные данные
4
Выходные данные
8

Условия всех задач турнира (pdf)


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Межвузовские олимпиады / XXI межвузовская олимпиада /
1850. E - Обработка видео 1851. 1852. G - Кратчайший путь 1853. H - Двоичное дерево 1854. I - Гири
 
время генерации 0.063 сек.
© Copyright ВоГУ, АВТ, Носов Д.А.