Golden Radio Base （模拟+推公式）

Golden ratio base (GRB) is a non-integer positional numeral system that uses the golden ratio (the irrational number (1+√5)/2 ≈ 1.61803399 symbolized by the Greek letter φ) as its base. It is sometimes referred to as base-φ, golden mean base, phi-base, or, phi-nary.

Any non-negative real number can be represented as a base-φ numeral using only the digits 0 and 1, and avoiding the digit sequence "11" – this is called a standard form. A base-φ numeral that includes the digit sequence "11" can always be rewritten in standard form, using the algebraic properties of the base φ — most notably that φ + 1 = φ 2 . For instance, 11(φ) = 100(φ). Despite using an irrational number base, when using standard form, all on-negative integers have a unique representation as a terminating (finite) base-φ expansion. The set of numbers which possess a finite base-φ representation is the ring Z[1 + √5/2]; it plays the same role in this numeral systems as dyadic rationals play in binary numbers, providing a possibility to multiply.

Other numbers have standard representations in base-φ, with rational numbers having recurring representations. These representations are unique, except that numbers (mentioned above) with a terminating expansion also have a non-terminating expansion, as they do in base-10; for example, 1=0.99999….

Coach MMM, an Computer Science Professor who is also addicted to Mathematics, is extremely interested in GRB and now ask you for help to write a converter which, given an integer N in base-10, outputs its corresponding form in base-φ.

Input

There are multiple test cases. Each line of the input consists of one positive integer which is not larger than 10^9. The number of test cases is less than 10000. Input is terminated by end-of-file.

Output

For each test case, output the required answer in a single line. Note that trailing 0s after the decimal point should be wiped. Please see the samples for more details.

Sample Input

1
2
3
6
10

Sample Output

1
10.01
100.01
1010.0001
10100.0101

        
  

Hint

题目中给出两个公式，手推一下前几项，可以发现两个规律：

φ^n+φ^(n+1)=φ^(n+2)

2*(φ^n)=φ^(n+1)+φ^(n-2)

然后一直模拟就好了

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+50;
int a[N];
int main()
{
    long long n;
    while(scanf("%lld",&n)!=EOF)
    {
        memset(a,0,sizeof(a));
        a[50]=n;///把原数放到某一位，两侧留出足够空间， 因为会出现小数部分
        bool flag=1;///用于标记是否还需循环
        while(flag)
        {
            flag=0;
            for(int i=0;i<100;i++)
            {
                if(a[i]&&a[i+1])
                {
                    int minn=min(a[i],a[i+1]);///一次性进位完，取二者中的较小值，加到i+2位
                    a[i+2]+=minn;
                    a[i]-=minn;
                    a[i+1]-=minn;
                    flag=1;///现在进行了这一步操作，说明接下来还有可能需要继续进位或拆分到两项里，再循环
                }
            }
            for(int i=2;i<100;i++)
            {
                if(a[i]>1)
                {
                    int x=a[i]/2;///一次性拆分完，求a[i]可以拆到a[i+1] a[i-2]里几个
                    a[i]%=2;
                    a[i+1]+=x;
                    a[i-2]+=x;
                    flag=1;///还需循环
                }
            }
        }
        int st,ed;///找到起始位置与终止位置
        for(int i=100;i>=0;i--)
        {
            if(a[i])
            {
                st=i;
                break;
            }
        }
        for(int i=0;i<100;i++)
        {
            if(a[i])
            {
                ed=i;
                break;
            }
        }
        for(int i=st;i>=ed;i--)
        {
            if(i==49)///输出小数点
                cout<<".";
            cout<<a[i];
        }
        cout<<'\n';
    }
    return 0;
}