/ Vijos / 题库 /

cpc的逃离

cpc的逃离

背景

可爱的cpc小朋友正进行着他的寻找恐龙之旅,他遇到了一系列的困难。。。。

描述

小朋友cpc来到了恐龙之旅的出发点,遇到了一个非常恐怖的怪物。

怪物说:“你必须回答我出的一个问题,否则你就将被XXX”
可以用下面的方案给二叉树标号:
空树的序号为0。

只有一个根结点的树序号为1。

所有包含m个结点的二叉树的序号一定比任何一个包含m+1个结点的二叉树的序号小。

任何一棵二叉树其左子树序号为L,右子树序号为R,且它有m个结点,若它的序号为n,则所有序号大于n的且有m个结点的二叉树必满足下列条件之一:
—— 左子树序号大于L
—— 左子树序号等于L且右子树序号大于R

头5棵二叉树的形状如下:
说明
你的任务就是对给定的序号,输出该序号所对应的二叉树。

格式

输入格式

输入文件包含多组数据,每个数据只有一个单独的整数n(1<= n <=500,000,000)。当n=0时表示输入文件结束,但你不必输出n=0时的空树。

输出格式

对每个数据产生一个输出。每个数据仅须输出一行,表示对应序号的树。

输出树时使用下列格式:
一棵树若没有子树则输出根:X。

一棵树有左子树L和右子树R应当输出:(L')X(R'),L'和R'为序号L和R对应的二叉树。当然,若L=0则输出X(R');若R=0则输出(L')X。

样例1

样例输入1

43
3254
233212
0

样例输出1

(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

样例输入2

1
2
3
4
5
0

样例输出2

X
X(X)
(X)X
X(X(X))
X((X)X)

限制

ONLY 1S,可怜的cpc。。。。

提示

你能帮一帮cpc吗?
注意x全是大写哦。。。。

信息

ID
1400
难度
2
分类
组合数学 | Catalan数列 点击显示
标签
(无)
递交数
166
已通过
95
通过率
57%
上传者

相关