pku1095.c

#include <stdio.h>
#define M_MAX 18

int m[M_MAX],k[M_MAX];

void doit(int n){
  int i=0,j=0,a,l,r,nl,nr;
  if(n==1){printf("X");return;}

  for(i=0;n>k[i];i++);
  a=i;
  for(i=j=0;n>j+k[a-1];i++)
    j+=m[i]*m[a-i-1];

  l=i-1;r=a-i;

  if(l==0){
    printf("X(");
    doit(n-k[a-1]+k[r-1]);
    printf(")");
  }else if(r==0){
    printf("(");
    doit(n-(k[a]-m[a-1])+k[l-1]);
    printf(")X");
  }else{
    int aho = n-k[a-1]-j+m[r]*m[l];
    nl=(aho-1)/m[r]+1;
    nr=aho%m[r]+1;
    printf("(");
    doit(nl+k[l-1]);
    printf(")X(");
    doit(nr+k[r-1]);
    printf(")");
  }
}

int main(){
  int i,j,n;
  m[0]=m[1]=1;
  for(i=2; i<=M_MAX; i++)
    for(j=0; j<i; j++)
      m[i] += m[j]*m[i-j-1];
  for(i=1;i<=M_MAX;i++)
    k[i] += m[i]+k[i-1];    
  for(;;){
    scanf("%d",&n);
    if(!n)break;
    doit(n);
    printf("\n");
  }
  return 0;
}