[ZJ a134][UVA 00948] Fibonaccimal Base

原題： a134. 00948 - Fibonaccimal Base - 高中生程式解題系統 (zerojudge.tw)

解題方向：觀察、進位制

根據觀察，如果我們把一個數字去盡可能大的費式數，就能構造題目要求沒有連續 $1$ 的答案。

證明：

設 $x$ 足夠大，能被兩個相鄰的費式數夾擠，也就是 $F_{n+1}>x \geq F_{n}$。

如果要有不相鄰的 $1$ ，那麼 $x-F_{n}$ 就要小於 $F_{n-1}$。

根據定義

$F_{n+1}=F_{n}+F_{n-1} > x$

移項

$F_{n-1} > x - F_{n}$

故得證。

#include<bits/stdc++.h>
using namespace std;

int main() {
    long long f[40] = {1, 2, 0};
    for(int i=2;i<40;++i)
        f[i] = f[i-1] + f[i-2];
    reverse(f, f+40);

    int N, x;
    cin >> N;
    while (N--) {
        cin >> x;
        cout << x << " = ";

        bool leadZero = true;
        for(long long v:f) {
            if (x >= v) {
                leadZero = false;
                cout << 1;
                x-=v;
            } else {
                if (!leadZero) cout << 0;
            }
        }

        cout << " (fib)\n";
    }
    return 0;
}