Задача №1767. Треугольник Паскаля
В олимпиаде всего 6 заданий. По сложности НЕ ОТСОРТИРОВАНЫ
A) Алгебра с ифом.
B) Нужно знать конструкцию FOR и уметь подсчитывать количество, суммы и т.п. (n-натуральное число типа longint);
C) Конструкция while и системы счисления(на вход подается неотрицательное целое число до 2^31-1).
D) Можно решить даже без цикла (но наиболее распространенным будет решение через While).
E) Решается даже только алгеброй и ифами.
F)Намного больше знаний и смекалки.
Тут нужно заметить закономерность и применить либо рекурсию, либо динамику, либо формулу (последний способ связан с системами счисления,этот вариант самый крутой по скорости легкий в реализации, но попробуй додумайся).
Удачи!!!
Драганов А.В.
PS
Результаты сразу после олимпиады. Дорешивание будет открыто.
Треугольник Паскаля – это бесконечный треугольник из чисел, который имеет следующий вид:
Строки треугольника Паскаля нумеруются с нуля, числа в каждой строке также нумеруются с нуля. Нулевая строка содержит единственное число – единицу, а каждая следующая содержит на одно число больше, чем предыдущая. Нулевое и последнее число в каждой строке равны единице, а каждое из остальных равно сумме двух чисел предыдущей строки, расположенных над ним.
Таким образом, \(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\)-ой строке треугольника Паскаля.
0
1
5
4
7
8