|
Trees Made to Order
| Time Limit: 1000MS |
|
Memory Limit: 10000K |
| Total Submissions: 6010 |
|
Accepted: 3459 |
Description
We can number binary trees using the following scheme:
The empty tree is numbered 0.
The single-node tree is numbered 1.
All binary trees having m nodes have numbers less than all those having m+1
nodes.
Any binary tree having m nodes with left and right subtrees L and R
is numbered n such that all trees having m nodes numbered > n have either
Left subtrees numbered higher than L, or A left subtree = L and a right subtree
numbered higher than R.
The first 10 binary trees and tree number 20 in
this sequence are shown below:
Your job for this problem
is to output a binary tree when given its order number.
Input
Input consists of multiple problem instances. Each
instance consists of a single integer n, where 1 <= n <= 500,000,000. A
value of n = 0 terminates input. (Note that this means you will never have to
output the empty tree.)
Output
For each problem instance, you should output one line
containing the tree corresponding to the order number for that instance. To
print out the tree, use the following scheme:
A tree with no children
should be output as X.
A tree with left and right subtrees L and R should be
output as (L')X(R'), where L' and R' are the representations of L and R.
If
L is empty, just output X(R').
If R is empty, just output (L')X.
Sample Input
1
20
31117532
0
Sample Output
X
((X)X(X))X
(X(X(((X(X))X(X))X(X))))X(((X((X)X((X)X)))X)X)
Source
|
不錯的題目
考察卡特蘭數(shù)的遞歸式的
等會把找到的卡特蘭數(shù)的資料發(fā)一篇上來
code
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <sstream>
#include <fstream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#include <iomanip>
using namespace std;
long long dx[20]={1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790,477638700,1767263190};
void dg(long long n,long long k)
{
int i;
long long sum;
if(n==1)
{
printf("X");
return ;
}
sum=0;
for(i=0;k>sum;i++) sum+=dx[i]*dx[n-i-1];
i=i-1;
sum-=dx[i]*dx[n-i-1];
k-=sum;
//printf("%d %d %d\n",n,k,i);
if(i)
{
printf("(");
dg(i,(k-1)/dx[n-i-1]+1);//沒有也是一種
printf(")");
}
printf("X");
if(n-i-1)
{
printf("(");
dg(n-i-1,(k-1)%dx[n-i-1]+1);
printf(")");
}
}
int main()
{
int i;
long long n;
long long sum;
while(scanf("%I64d",&n)!=EOF&&n!=0)
{
if(n==1)
{
printf("X\n");
}
else
{
sum=0;
for(i=1;n>sum;i++) sum+=dx[i];
i--;
sum-=dx[i];
dg(i,n-sum);
printf("\n");
}
}
return 0;
}