提示: 欢迎访问OurACM平台
Problem 1064 教授的测试

Accept: 162    Submit: 404
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

一年一度的研究生面试又快要来临了。为了测试学生对树结构的认识,同时也检验他们的编程能力,福州大学计算机系把面试的一项内容定为:要求学生们编程按编号顺序打印出节点个数不少于m的所有二叉树。
二叉树编号规则如下:

  • 仅有一个节点的树编号为1。
  • 当满足以下条件之一时,定义二叉树a的编号比b大: 1. a的节点数比b多。 2. 若a的节点数与b相等,且a的左子树编号比b的左子树大。 3. a的节点数和左子树编号都和b相等,且a的右子树编号比b的右子树大。
  • 二叉树的节点用大写X表示,例如:
    当然当m较大时,检验答案对错的工作也是很繁重的,所以教授只打算对其中的若干个编号的二叉树进行抽查,他想麻烦你编制一个程序能够产生编号为n的二叉树的标准答案。

    Input

    输入数据由多组数据组成。每组数据仅一个整数,表示n (1≤n≤10^8)的值。输入数据以n=0表示结束,该数据不要处理。

    Output

    对于每组数据,输出仅一行,即你求出的标准答案。
    二叉树的输出格式为:
    (左子树){若左子树为空则省略}X{根}(右子树){若右子树为空则省略}
    其中{…}中的内容是说明,不必输出。例如,在上图中编号为5的树可表示为X((X)X);编号为6的树表示为(X)X(X)。

    Sample Input

    20 0

    Sample Output

    ((X)X(X))X

    Source

    FZUPC 2005

    Submit  Back  Status  Discuss