https://code.google.com/codejam/contest/4214486/dashboard#s=p3

GCJ2014B_2.cpp

#include <iostream>
#include <vector>
#include <string>
using namespace std;

/*
Small data test pass
*/
typedef long long llong;

const int LIMIT = 100;
llong dp[LIMIT+1][LIMIT+1];

void buildMatrix() {
    for (int i = 0; i <= LIMIT; i++) {
        for (int j = i; j <= LIMIT; j++) {
            if (i == 0) {
                dp[i][j] = 1;
            } else {
                dp[i][j] = dp[i-1][j];
                if (i < j) {
                    dp[i][j] += dp[i][j-1];
                }    
            }
        }
    }
}

int main() {
    int T;
    cin >> T;
    buildMatrix();
    for (int i = 1; i <= T; i++) {
        int n;
        llong k;
        cin >> n >> k;

        // solve
        string s;
        int a = n;
        int b = n;
        while (k > 0 && a > 0) {
            //cout << "k:" << k << ", dp[" << a << "," << b << "]:" << dp[a][b] << endl;
            if (a == b) {
                s += '(';
                a--;
            } else if (k <= dp[a-1][b]) {
                s += '(';
                a--;
            } else {
                s += ')';
                k -= dp[a-1][b];
                b--;
            }
        }
        // cout << "a:" << a << endl;
        if (a == 0 && k == 1) {
            while (b--) {
                s += ')';
            }
        } else {
            s = "Doesn't Exist!";
        }
        cout << "Case #" << i << ": " << s << endl;

    }

}