Задача №111837. Количество вызовов функции Фиббоначи
Как известно, очередное число Фиббоначи равно сумме предыдущих двух. Первое и второе число Фиббоначи равны единице.
Программист Вася написал вычисление n-ого числа Фиббоначи с помощью рекурсивной функции. А как долго придется ждать Васе, прежде чем будет получено значение?
Входные данные
Дано одно число n ( 1 ≤ n ≤ 10 6 )
Выходные данные
Выведите одно число — целую часть от деления числа k на 1000000000 , где k — количество запусков функции Фиббоначи.
Примеры
Входные данные
3
Выходные данные
0
Входные данные
100
Выходные данные
29
Сдать: для сдачи задач необходимо войти в систему