printРабочее место участника

printЗадачи

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

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Треугольник Паскаля — это бесконечный треугольник из чисел, который имеет следующий вид:
1456.gif
Строки треугольника Паскаля нумеруются с нуля, числа в каждой строке также нумеруются с нуля. Нулевая строка содержит единственное число — единицу, а каждая следующая содержит на одно число больше, чем предыдущая. Нулевое и последнее число в каждой строке равны единице, а каждое из остальных равно сумме двух чисел предыдущей строки, расположенных над ним.
Таким образом, `i`-ая строка содержит `i\ +\ 1` число. Если обозначить `j`-ый элемент `i`-ой строки как `a_{i,j}`, то выполняется равенство `a_{i,j}\ =\ a_{i-1,j-1}\ +\ a_{i-1,j}`. Заметим, что это равенство выполняется и для крайних элементов, если положить отсутствующие элементы предыдущей строки (элементы с номерами `-1` и `i`) равными нулю.
Коля хочет узнать, сколько нечетных чисел в `n`-ой строке треугольника Паскаля. Он начал рисовать треугольник, но очень скоро тот перестал помещаться на листочек. Тогда Коля решил сделать это с помощью компьютера. Помогите ему.
Ввод
Во входном файле содержится число `n` (`0\ ≤\ n\ ≤\ 2⋅10^9`).
Вывод
Выходной файл должен содержать одно число — количество нечетных чисел в `n`-ой строке треугольника Паскаля.

Пример ввода 1

0

Пример вывода 1

1

Пример ввода 2

5

Пример вывода 2

4

Пример ввода 3

7

Пример вывода 3

8
Источник: XII командный чемпионат школьников Санкт-Петербурга по программированию.
loading