时间限制:1000 ms
内存限制:128 MiB
标准输入输出
题目类型:传统
评测方式:无测试数据
一本“奇怪的数学书”上记载了这样一种正整数→二叉树的一一对应。
每棵二叉树用一个只含有的字符串X,(,)表示,每个X表示一个节点。每个X左右都可以有或没有一对括号,这对括号内的字符串表示这个节点的左子树或者右子树。每对括号内的子树以递归的满足上述定义。
比如说字符串(X)X(X(X))表示的就是这样一颗二叉树
树与数的对应法则是这样的:
每棵树唯一对应一个数字,每个数唯一对应一棵树;
只有一个节点的树是1;
树的节点个数越多数字大;
节点数相同的树比较左子树,左子树完全相同的比较右子树。
可见这个比较是递归进行的。
我们可以画出前几个树:
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| | | | | | | | | | |
X | X | X | X | X | X | X | X | X | X | X |
| \ | / | \ | \ | / \ | / | / | \ | \ | \ |
| X | X | X | X | X X | X | X | X | X | X | ......
| \ | / | | \ | / | \ | \ | / \ |
| X | X | | X | X | X | X | X X |
| \ | / |
| X | X |
现在你的任务很简单,只需要把数转化为对应的树,用字符串形式输出即可。
有多组测试数据,对于每组测试数据:只有一行,包含一个正整数N,表示需要转化的数。
输入文件以一行一个数字结束0,你不需要将0转化为树输出。
对每组数据输出一行,包含一个字符串,表示转化成的树。
样例输入:
样例输出:
X
X(X)
(X)X
X(X(X))
X((X)X)
(X)X(X)
(X(X))X
((X)X)X
X(X(X(X)))
1<=N<=10^16,,每个输入文件测试数据不超过100000组。