2015
04-14

# Extend-Tree

There are many questions about the tree, most of them are Binary tree. But now, I’m tired of it. In this problem, we will not talk about the binary tree again, we discuss the tree which has three sub-trees, we called it extend tree;

The extend tree is orderly, it means that every integer n(n>=0) correspond to one unique extend tree and each extend tree correspond to one unique number. The tree is numbered using the following scheme:

1. The empty tree is numbered 0;
2. The single-node tree is numbered 1;
3. All extend trees that has m nodes correspond to a smaller integer than the tree which has more than m nodes.
4. Any extend tree having m nodes with left, mid and right sub-trees L ,M and R is numbered n; such that all trees having m nodes numbered > n have either Left sub-trees numbered higher than L, or A left sub-tree = L and a mid sub-tree numbered higher than M, or a left sub-tree = L a mid sub-tree = M and a right sub-tree numbered higher than R.

The first 18 extend trees are show below:

Your job for this problem is to output a extend tree when its order number is given.

The first line contains a single positive integer T( T <= 3000 ), indicating the number of datasets.
Each instance consist of a single integer n, where 1<= n <=10^14.

The first line contains a single positive integer T( T <= 3000 ), indicating the number of datasets.
Each instance consist of a single integer n, where 1<= n <=10^14.

10
1
2
3
4
5
6
7
8
9
10

Case #1: X
Case #2: (X)X
Case #3: (X)X
Case #4: (X)X
Case #5: ((X)X)X
Case #6: ((X)X)X
Case #7: ((X)X)X
Case #8: (X)(X)X
Case #9: ((X)X)X
Case #10: ((X)X)X

#include<stdio.h>
#include<math.h>
typedef long long ll;
ll a[30],s[30];
void init(){
int i,j,k;
a[0]=a[1]=1;
s[0]=0;
for(i=2;i<=20;i++)
for(j=0;j<i;j++)
for(k=0;k<=i-1-j;k++)
a[i]+=a[j]*a[k]*a[i-1-j-k];
for(i=1;i<=20;i++)
s[i]=s[i-1]+a[i];
}
void cal(ll n,ll &rank,ll &num){
int i;
for(i=1;i<=20;i++)
if(s[i]>n)
break;
rank=n-s[i-1];
num=i;
}
void solve(ll num,ll rank){
ll i,j,k;
ll ii,jj,kk;
ll ss,tem;
if(num==1){
printf("X");
return ;
}
for(i=0;i<num;i++){
for(ss=0,j=0;j<num-i;j++)
ss+=a[j]*a[num-i-j-1];
if(ss*a[i]>rank){
ii=rank/ss;
rank%=ss;
break;
}
else
rank-=ss*a[i];
}
for(j=0;j<num-i;j++){
if(a[j]*a[num-i-1-j]>rank){
break;
}
else
rank-=a[j]*a[num-1-i-j];
}
if(i!=0){
printf("(");
solve(i,ii);
printf(")");
}
if(j!=0){
printf("(");
solve(j,rank/a[num-1-i-j]);
printf(")");
}
if(num-i-j-1!=0){
printf("(");
solve(num-1-i-j,rank%a[num-1-i-j]);
printf(")");
}
printf("X");
}
int main(){
int t,T;
ll n,rank,num;
//freopen( "E.in", "r", stdin );
//freopen( "a.txt", "w", stdout );
init();
scanf("%d",&T);
for(t=1;t<=T;t++){
printf("Case #%d: ",t);
scanf("%I64d",&n);        //%I64d被HDU坑死、、、、
cal(n-1,rank,num);
solve(num,rank);
printf("\n");
}
}

1. 老实说，这种方法就是穷举，复杂度是2^n，之所以能够AC是应为题目的测试数据有问题，要么数据量很小，要么能够得到k == t，否则即使n = 30，也要很久才能得出结果，本人亲测

2. 站长，你好！
你创办的的网站非常好，为我们学习算法练习编程提供了一个很好的平台，我想给你提个小建议，就是要能把每道题目的难度标出来就好了，这样我们学习起来会有一个循序渐进的过程！