Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Треугольник Паскаля — это бесконечный треугольник из чисел, который имеет
следующий вид:
Строки треугольника Паскаля нумеруются с нуля, числа в каждой строке также
нумеруются с нуля. Нулевая строка содержит единственное
число — единицу, а каждая следующая содержит на одно число больше,
чем предыдущая. Нулевое и последнее число в каждой строке равны единице,
а каждое из остальных равно сумме двух чисел предыдущей строки,
расположенных над ним.
Таким образом, `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`-ой
строке треугольника Паскаля.
Источник: XII командный чемпионат школьников Санкт-Петербурга по программированию.