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

1 人解决,8 人已尝试。

1 份提交通过,共有 31 份提交。

9.9 EMB 奖励。

创建: 11 年,12 月前.

修改: 3 年,3 月前.

最后提交: 13 小时前.

来源: NEERC 2008

题目标签