Подразделы

Другие разделы

Дата и время

09/04/2025 19:00:35

Авторизация

Лето 9

A. Катание на автобусах B. Старая крепость C. Гистограмма D. Два коня E. Сапер F. Интересное число G. Треугольник Паскаля H. Два прямоугольника I. Цветные нули

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

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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$ -ой строке треугольника Паскаля.

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

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

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

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

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

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