P1814 Index of a Binary Tree

We can label binary trees using the following scheme: - The empty tree has index $0$. - The tree with only a root node has index $1$. - All binary trees with $m$ nodes have indices smaller than any binary tree with $m+1$ nodes. - For any binary tree, let its left-subtree index be $L$, its right-subtree index be $R$, and it have $m$ nodes. If its index is $n$, then for all $m$-node binary trees whose indices are greater than $n$, either their left-subtree index is greater than $L$, or their left-subtree index equals $L$ and their right-subtree index is greater than $R$. For example, the six trees with indices $0$ through $5$ have the following shapes: ```plain 0 1 2 3 4 5 X X X X X \ / \ \ X X X X \ / X X ``` Your task is to output the binary tree corresponding to a given index.

This problem has multiple test cases. Each line contains a non-negative integer $n$. $n=0$ indicates the end of input, and you do not need to output the empty tree for $n=0$.

For each test case, output one line representing the tree corresponding to index $n$. A binary tree is represented as `(L)X(R)`, where $L$ and $R$ are the representations of the left and right subtrees, respectively. If one side is empty, omit it; for example, if there is only a left subtree, it is represented as `(L)X`.

### Constraints 对于所有测试点，保证 $1\le n\le 5\times10^8$，数据组数不超过 $50$。 Translated by ChatGPT 5