FIBOBASE - Fibonacci Counting System
English | Vietnamese |
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 |