# Poj Solution 1095

```http://poj.org/problem?id=1095

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;

public class Main {
static final int N = 20+10;
static int sum[] = new int[N],catana[] = new int[N];
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[]args) throws Exception{
int n;
init();
Scanner cin = new Scanner(System.in);
while(true){
n = cin.nextInt();
if(n==0) break;
solve(n);
out.println();
out.flush();
}
}
static void solve(int n){
int i,j,t;
if(n==0) return ;
if(n==1) {out.print("X");return;}
for(j=1;;++j){
if(sum[j]>=n) break;
}
n = n-sum[j-1];
for(i=0;i< j;++i){
t = catana[i]*catana[j-i-1];
if(n>t) n = n-t;
else break;
}
if(i!=0){
out.print("(");
solve(sum[i-1]+1+(n-1)/catana[j-i-1]);
out.print(")");
}
out.print("X");
if(i!=j-1){
out.print("(");
solve(sum[j-2-i]+1+(n-1)%catana[j-i-1]);
out.print(")");
}
}
static void init(){
int i,j;
catana = catana = 1;
for(i=2;i< N;++i){
catana[i] = 0;
for(j=0;j< i;++j){
catana[i] += catana[j]*catana[i-j-1];
}
}
sum = 0;
sum = 1;
for(i=2;i< N;++i)
sum[i] = sum[i-1]+catana[i];
}
}

```
This entry was posted in poj. Bookmark the permalink.