XII Командный чемпионат школьников Санкт-Петербурга по программированию
Ограничение времени:
2 сек
Входной файл:
pascal.in
Ограничение памяти:
8 Мб
Выходной файл:
pascal.out
Условие
Треугольник Паскаля — это бесконечный треугольник из чисел, который имеет
следующий вид:
1
1
1
1
2
1
1
3
3
1
1
4
6
4
1
…
…
…
…
…
…
Строки треугольника Паскаля нумеруются с нуля, числа в каждой строке также
нумеруются с нуля. Нулевая строка содержит единственное
число — единицу, а каждая следующая содержит на одно число больше,
чем предыдущая. Нулевое и последнее число в каждой строке равны единице,
а каждое из остальных равно сумме двух чисел предыдущей строки,
расположенных над ним.
Таким образом, i-ая строка содержит i + 1 число. Если
обозначить j-ый элемент i-ой строки как ai, j, то выполняется равенство
ai, j = ai−1, j−1 + ai−1, j. Заметим, что это равенство
выполняется и для крайних элементов, если положить отсутствующие элементы
предыдущей строки (элементы с номерами −1 и i) равными нулю.
Коля хочет узнать,
сколько нечетных чисел в n-ой строке треугольника Паскаля. Он начал рисовать треугольник,
но очень скоро тот перестал помещаться на листочек. Тогда Коля решил сделать это с помощью
компьютера. Помогите ему.
Формат входного файла
Во входном файле содержится число n.
Формат выходного файла
Выходной файл должен содержать одно число — количество нечетных чисел в n-ой
строке треугольника Паскаля.
