시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 20 16 15 78.947%

문제

다음과 과정을 거쳐서 바이너리 트리에 번호를 붙일 수 있다.

  • 비어있는 트리의 번호는 0이다.
  • 노드가 1개인 트리는 1번이다.
  • 노드가 m개인 바이너리 트리의 번호는 m+1개인 트리의 번호보다 작다.
  • 노드가 m개이고, 왼쪽과 오른쪽 서브트리가 각각 L과 R인 바이너리 트리의 번호 n은 아래와 같은 두 조건 중 하나라도 만족하는 트리보다 번호가 작다. 
    • 왼쪽 서브 트리가 L보다 번호가 크다. 또는
    • 왼쪽 서브 트리가 L과 같고, 오른쪽 서브트리가 R보다 번호가 크다.

처음 10개 바이너리 트리와 20번째 바이너리 트리를 그림으로 그려보면 아래와 같다.

        0  1  2      3  4      5      6      7      8  9        ...     20

           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이 주어졌을 때, n번째 바이너리 트리를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있으며, n이 하나 주어진다. (1 ≤ n ≤ 500,000,000) n=0인 경우에 프로그램을 종료하면 된다.

출력

각각의 n에 대해서, 트리를 아래와 같이 출력한다.

  • 자식이 없는 트리는 x로 출력한다.
  • 왼쪽, 오른쪽 서브트리가 L과 R이고, 각각을 출력한 결과가 L', R'일 때, (L')x(R')을 출력한다.
    • L이 비어잇으면 X(R')을 출력한다.
    • R이 비어있으면 (L')x를 출력한다.

예제 입력

1
20
31117532
0

예제 출력

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

힌트