FIBOBASE - Fibonacci Counting System

SM �ạc biệt say mê các dấng biᝃn diễn số nguyên trong các loấi hệ �ếm khác nhau.

Lần này SM dành khá nhiᝁu thời gian cho hệ �ếm Fibonacci nhị phân.

Nét �ạc biệt cᝧa hệ thống này là không có hai số 1 nào �ᝊng cấnh nhau.

Một số nguyên M có thᝃ biᝃu diễn dưới dấng

M10 = anan-1…a2a1F ;

trong ďż˝ó ai báşąng 0 hoạc 1, ai*ai-1= 0 và M = anFn + an-1Fn-1 + … + a2F2 + a1F1;

trong ďż˝ó F0 = F1 = 1, Fi = Fi-1 + Fi-2.

VD:

110 = 1F

210 = 10F

310 = 100F

410 = 101F

510 = 1000F

610 = 1001F

710 = 1010F

SM viáşżt liên tiáşżp các số táťą nhiên 1, 2, 3, … ở dấng hệ �ếm Fibonacci nhị phân

và �ưᝣc một sâu vô hấn các ký táťą  0, 1. Phần �ầu cᝧa xâu là 110100101100010011010…

Ngắm nhìn káşżt quả cᝧa mình SM táťą hỏi trong N chᝯ số �ầu tiên cᝧa dãy có bao nhiêu chᝯ số 1 ?

Cho số nguyên N. Hãy xác �ịnh số lưᝣng số 1 trong N chᝯ số �ầu tiên cᝧa dãy.

Input

Gồm 1 dòng chᝊa số nguyên N (0 <= N <= 1015).

Output

Káşżt quả tìm �ưᝣc ở dấng số nguyên.

Example

Input:

21

Output:

10

 


Added by:k[N]i[g]h[T]™
Date:2009-10-18
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 C++ 4.3.2 ERL NODEJS PERL6 VB.NET

hide comments
2020-02-29 15:00:09
Empty solution gets AC.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.