題目鏈接：uva 1350 - Pinary

題目大意:給出n，輸出第n給Pinary Number，Pinary Number為二進制數，並且沒有連續兩個1相連。

解題思路：dp[i]表示到第i位有dp[i]種，於是給定n，一層循環判斷dp[i]≤n的話，就輸出1，並且n減掉dp[i],注意輸出0的時候，不能輸出前導0.

#include 
#include 

typedef long long ll;
const int N = 50;
ll dp[N];

void init () {
    memset(dp, 0, sizeof(dp));
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= 40; i++)
        dp[i] = dp[i-1] + dp[i-2];
}

void solve (ll n) {
    bool flag = false;    

    for (int i = 40; i; i--) {
        if (n >= dp[i]) {
            printf("1");
            n -= dp[i];
            flag = true;
        } else if (flag)
            printf("0");
    }
    printf("\n");
}

int main () {
    init ();
    int cas;
    ll n;
    scanf("%d", &cas);
    for (int i = 0; i < cas; i++) {
        scanf("%lld", &n);
        solve(n);
    }
    return 0;
}