HDOJ 4814 Golden Radio Base

利用題目中給出的公式和hint可以得到兩個有用的公式：
phi^(n) = phi^(n-1)+phi^(n-2)
2*(phi^n) = phi^(n+1)+phi^(n-2)
可以計算出phi^100遠大於10^9，所以推測最後得到的phi進制的數整數和小數部分應該不會超過100位，事實表明，50位就能過。
所以最終變成了簡單的模擬。

Golden Radio Base

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 363 Accepted Submission(s): 165


Problem Description 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 = φ ² . 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 <喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcHJlPgoKCiAKPGJyPgoKU291cmNlCgoyMDEzIEFzaWEgUmVnaW9uYWwgQ2hhbmdjaHVuCgogCjxicj4KCjxicj4KPHA+PC9wPgo8cD48YnI+CjwvcD4KPHA+PHByZSBjbGFzcz0="brush:java;">#include 
#include 
#include 
#include 

using namespace std;

const int base=100;

int n;
int wei[220];

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        memset(wei,0,sizeof(wei));
        wei[base]=n;

        while(true)
        {
            bool flag=false;
            for(int i=0;i<200;i++)
            {
                if(wei[i]>1)
                {
                    int t=wei[i];
                    wei[i]=t%2;
                    wei[i+1]+=t/2;
                    wei[i-2]+=t/2;
                    flag=true;
                }
            }
            for(int i=0;i<200;i++)
            {
                if(wei[i]&&wei[i+1])
                {
                    int t=min(wei[i],wei[i+1]);
                    wei[i]-=t; wei[i+1]-=t;
                    wei[i+2]+=t;
                    flag=true;
                }
            }
            if(flag==false) break;
        }
        int st=-1,ed=-1;
        for(int i=0;i<202;i++)
            if(wei[i]) { st=i; break; }
        for(int i=202;i>=0;i--)
            if(wei[i]) { ed=i; break; }
        for(int i=ed;i>=st;i--)
        {
            printf("%d",wei[i]);
            if(i==base&&st!=i) putchar('.');
        }
        putchar(10);
    }
    return 0;
}