2015
09-18

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" �C 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-φ.

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.

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.

1
2
3
6
10

1
10.01
100.01
1010.0001
10100.0101
Hint 

x^(i+1) + x^i = x^(i+2)

2 * x^i = x^(i+1) + x^(i-2)

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100

int a[N*2];
int n,u,v;

int main()
{
int i,k,flag;
while(~scanf("%d",&n))
{
memset(a,0,sizeof(a));
a[N]=n;
do
{
flag=0;
for(i=0;i<N*2-2;i++)
{
if(a[i]&&a[i+1])
{
k=min(a[i],a[i+1]);
a[i]-=k;
a[i+1]-=k;
a[i+2]+=k;
flag=1;
}
}
for(i=2;i<N*2-1;i++)
{
if(a[i]>1)
{
k=a[i]/2;
a[i]%=2;
a[i-2]+=k;
a[i+1]+=k;
flag=1;
}
}
}while(flag);
for(u=2*N-1;u>N&&!a[u];u--);
for(v=0;v<N&&!a[v];v++);
for(i=u;i>=N;i--) printf("%d",a[i]);
if(v!=N)
{
printf(".");
for(i=N-1;i>=v;i--) printf("%d",a[i]);
}
printf("\n");
}
return 0;
}