Функция
(Время: 1 сек. Память: 16 Мб Сложность: 42%)
Функция f(n) определена следующим образом:
f(0)=0, f(1)=1, f(2n)=f(n), f(2n+1)=f(n)+f(n+1).
Требуется написать программу, которая по заданному натуральному числу N определяет значение функции f(N).
Входные данные
Входной файл INPUT.TXT содержит число N (1 ≤ N ≤ 2147483647).
Выходные данные
В выходной файл OUTPUT.TXT выведите значение f(N).
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2 | 1 |
| 2 | 5 | 3 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
