MALFORMA - SPOJ Br (Lazera)

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

#define TRACE(x...) x
#define PRINT(x...) TRACE(printf(x))
#define WATCH(x) TRACE(cout << #x << " = " << x << endl;)

#define MAXN 60

char v[MAXN];
long long pd[MAXN][MAXN];
long long cat[MAXN];

long long f(int n, int folga) {
    if(folga > n || folga < 0) return 0;
    if(n == 0) return 0;
    if(folga == n) return 1;
    if(pd[n][folga] != -1) return pd[n][folga];

    pd[n][folga] = f(n-1, folga+1); //ponho "("

    if(folga > 0) //ponho ")"
        pd[n][folga] += f(n-1, folga-1);

    return pd[n][folga];
}

long long f2(int n, int folga) {
    long long p2 = 1;
    for(int i = 1; i <= n; i++) p2 *= 2;
    return p2 - f(n, folga);
}

void preenche(int n, int k, int folga) {
    if(n == 0) return;
    printf("n, k, folga, f1(n-1, folga+1) = %d, %d, %d, %lld\n",
        n, k, folga, f2(n-1, folga+1));
    if( f2(n-1, folga+1) >= k ) {
        v[n] = '0';
        preenche(n-1, k, folga+1);
    }

    else {
        v[n] = '1';
        k -= f2(n-1, folga+1);
        preenche(n-1, k, folga-1);
    }
}

void calc() {
    memset(cat, 0, sizeof(cat));
    cat[2] = 1;
    cat[1] = 0;
    cat[0] = 1;
    for(int i = 3; i <= 51; i++) {
        if(i%2 == 1) continue;
        for(int j = 0; j < i; j+=2)
            cat[i] += cat[j]*cat[i-2-j];
    }
}

int main() {
    int T, N, K;
    calc();
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d", &N, &K);

        for(int i = 0; i < MAXN; i++)
            for(int j = 0; j < MAXN; j++)
                pd[i][j] = -1;

        v[N] = '?';
        K++; //indexo a partir do 1
        // ateh aqui nada
        for(int i = 2; i <= 10; i++) printf("cat = %lld\n", cat[i]);

        if( K <= ( (1LL<<N) - cat[N]) ) preenche(N, K, 0);

        if(v[N] == '?') printf("-1");
        else
            for(int i = N; i > 0; i--)
                printf("%c", v[i]);
        printf("\n");
    }

    return 0;
}