1 人解决，8 人已尝试。
1 份提交通过，共有 31 份提交。
9.9 EMB 奖励。
2717. Fibonacci System
单点时限: 5.0 sec
内存限制: 256 MB
Little John studies numeral systems. After learning all about fixed-base systems, he became interested in more unusual cases. Among those cases he found a Fibonacci system, which represents all natural numbers in an unique way using only two digits: zero and one. But unlike usual binary scale of notation, in the Fibonacci system you are not allowed to place two 1s in adjacent positions.
John wrote a very long string (consider it infinite) consisting of consecutive representations of natural numbers in Fibonacci system. For example, the first few digits of this string are 110100101100010011010. . .
He is very interested, how many times the digit 1 occurs in the N-th prefix of the string. Remember that the N-th prefix of the string is just a string consisting of its first N characters.
Write a program which determines how many times the digit 1 occurs in N-th prefix of John’s string.
输入格式
The input file contains a single integer N (0<N<10^15).
输出格式
Output a single integer ― the number of 1s in N-th prefix of John’s string.
样例
Input
21
Output
10
题目标签