시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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

1
20
31117532
0

예제 출력 1

X
((X)X(X))X
(X(X(((X(X))X(X))X(X))))X(((X((X)X((X)X)))X)X)
W3sicHJvYmxlbV9pZCI6IjczNTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQyYjhcdWI5YWNcdWM3NTggXHVjMjFjXHVjMTFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIyZTRcdWM3NGNcdWFjZmMgXHVhY2ZjXHVjODE1XHVjNzQ0IFx1YWM3MFx1Y2NkMFx1YzExYyBcdWJjMTRcdWM3NzRcdWIxMDhcdWI5YWMgXHVkMmI4XHViOWFjXHVjNWQwIFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWJkOTlcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWJlNDRcdWM1YjRcdWM3ODhcdWIyOTQgXHVkMmI4XHViOWFjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCAwXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWIxNzhcdWI0ZGNcdWFjMDAgMVx1YWMxY1x1Yzc3OCBcdWQyYjhcdWI5YWNcdWIyOTQgMVx1YmM4OFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViMTc4XHViNGRjXHVhYzAwIG1cdWFjMWNcdWM3NzggXHViYzE0XHVjNzc0XHViMTA4XHViOWFjIFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgbSsxXHVhYzFjXHVjNzc4IFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWJjZjRcdWIyZTQgXHVjNzkxXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWIxNzhcdWI0ZGNcdWFjMDAgbVx1YWMxY1x1Yzc3NFx1YWNlMCwgXHVjNjdjXHVjYWJkXHVhY2ZjIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWMxMWNcdWJlMGNcdWQyYjhcdWI5YWNcdWFjMDAgXHVhYzAxXHVhYzAxIExcdWFjZmMgUlx1Yzc3OCBcdWJjMTRcdWM3NzRcdWIxMDhcdWI5YWMgXHVkMmI4XHViOWFjXHVjNzU4IFx1YmM4OFx1ZDYzOCBuXHVjNzQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHViNDUwIFx1Yzg3MFx1YWM3NCBcdWM5MTEgXHVkNTU4XHViMDk4XHViNzdjXHViM2M0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWQyYjhcdWI5YWNcdWJjZjRcdWIyZTQgXHViYzg4XHVkNjM4XHVhYzAwIFx1Yzc5MVx1YjJlNC4mbmJzcDtcclxuXHQ8dWw+XHJcblx0XHQ8bGk+XHVjNjdjXHVjYWJkIFx1YzExY1x1YmUwYyBcdWQyYjhcdWI5YWNcdWFjMDAgTFx1YmNmNFx1YjJlNCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVkMDZjXHViMmU0LiBcdWI2MTBcdWIyOTQ8XC9saT5cclxuXHRcdDxsaT5cdWM2N2NcdWNhYmQgXHVjMTFjXHViZTBjIFx1ZDJiOFx1YjlhY1x1YWMwMCBMXHVhY2ZjIFx1YWMxOVx1YWNlMCwgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzExY1x1YmUwY1x1ZDJiOFx1YjlhY1x1YWMwMCBSXHViY2Y0XHViMmU0IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWQwNmNcdWIyZTQuPFwvbGk+XHJcblx0PFwvdWw+XHJcblx0PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjYzk4XHVjNzRjIDEwXHVhYzFjIFx1YmMxNFx1Yzc3NFx1YjEwOFx1YjlhYyBcdWQyYjhcdWI5YWNcdWM2NDAgMjBcdWJjODhcdWM5ZjggXHViYzE0XHVjNzc0XHViMTA4XHViOWFjIFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWFkZjhcdWI5YmNcdWM3M2NcdWI4NWMgXHVhZGY4XHViODI0XHViY2Y0XHViYTc0IFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgICAgICAgMCAgMSAgMiAgICAgIDMgIDQgICAgICA1ICAgICAgNiAgICAgIDcgICAgICA4ICA5ICAgICAgICAuLi4gICAgIDIwXHJcblxyXG4gICAgICAgICAgIFggIFggICAgICBYICBYICAgICAgWCAgICAgIFggICAgICBYICAgICAgWCAgWCAgICAgICAgICAgICAgICAgWFxyXG4gICAgICAgICAgICAgICBcXCAgICBcLyAgICBcXCAgICAgIFxcICAgIFwvIFxcICAgIFwvICAgICAgXC8gICAgXFwgICAgICAgICAgICAgICBcL1xyXG4gICAgICAgICAgICAgICAgWCAgWCAgICAgIFggICAgICBYICBYICAgWCAgWCAgICAgIFggICAgICBYICAgICAgICAgICAgIFhcclxuICAgICAgICAgICAgICAgICAgICAgICAgICAgXFwgICAgXC8gICAgICAgICAgIFxcICAgIFwvICAgICAgICBcXCAgICAgICAgICAgXC8gXFxcclxuICAgICAgICAgICAgICAgICAgICAgICAgICAgIFggIFggICAgICAgICAgICAgWCAgWCAgICAgICAgICBYICAgICAgICAgWCAgIFhcclxuICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgXFxcclxuICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIFhcclxuPFwvcHJlPlxyXG5cclxuPHA+blx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBuXHViYzg4XHVjOWY4IFx1YmMxNFx1Yzc3NFx1YjEwOFx1YjlhYyBcdWQyYjhcdWI5YWNcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIG5cdWM3NzQgXHVkNTU4XHViMDk4IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBuICZsZTsgNTAwLDAwMCwwMDApIG49MFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzg4NVx1YjhjY1x1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IG5cdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWQyYjhcdWI5YWNcdWI5N2MgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjNzkwXHVjMmRkXHVjNzc0IFx1YzVjNlx1YjI5NCBcdWQyYjhcdWI5YWNcdWIyOTQgeFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzY3Y1x1Y2FiZCwgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzExY1x1YmUwY1x1ZDJiOFx1YjlhY1x1YWMwMCBMXHVhY2ZjIFJcdWM3NzRcdWFjZTAsIFx1YWMwMVx1YWMwMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWMgXHVhY2IwXHVhY2ZjXHVhYzAwIEwmIzM5OywgUiYjMzk7XHVjNzdjIFx1YjU0YywgKEwmIzM5Oyl4KFImIzM5OylcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LlxyXG5cdDx1bD5cclxuXHRcdDxsaT5MXHVjNzc0IFx1YmU0NFx1YzViNFx1Yzc4N1x1YzczY1x1YmE3NCBYKFImIzM5OylcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdFx0PGxpPlJcdWM3NzQgXHViZTQ0XHVjNWI0XHVjNzg4XHVjNzNjXHViYTc0IChMJiMzOTspeFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PFwvdWw+XHJcblx0PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI3MzU0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVHJlZXMgTWFkZSB0byBPcmRlciIsImRlc2NyaXB0aW9uIjoiPHA+V2UgY2FuIG51bWJlciBiaW5hcnkgdHJlZXMgdXNpbmcgdGhlIGZvbGxvd2luZyBzY2hlbWU6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+VGhlIGVtcHR5IHRyZWUgaXMgbnVtYmVyZWQgMC48XC9saT5cclxuXHQ8bGk+VGhlIHNpbmdsZS1ub2RlIHRyZWUgaXMgbnVtYmVyZWQgMS48XC9saT5cclxuXHQ8bGk+QWxsIGJpbmFyeSB0cmVlcyBoYXZpbmcgbSBub2RlcyBoYXZlIG51bWJlcnMgbGVzcyB0aGFuIGFsbCB0aG9zZSBoYXZpbmcgbSArIDEgbm9kZXMuPFwvbGk+XHJcblx0PGxpPkFueSBiaW5hcnkgdHJlZSBoYXZpbmcgbSBub2RlcyB3aXRoIGxlZnQgYW5kIHJpZ2h0IHN1YnRyZWVzIEwgYW5kIFIgaXMgbnVtYmVyZWQgbiBzdWNoIHRoYXQgYWxsIHRyZWVzIGhhdmluZyBtIG5vZGVzIG51bWJlcmVkICZndDsgbiBoYXZlIGVpdGhlclxyXG5cdDx1bD5cclxuXHRcdDxsaT5sZWZ0IHN1YnRyZWVzIG51bWJlcmVkIGhpZ2hlciB0aGFuIEwsIG9yPFwvbGk+XHJcblx0XHQ8bGk+YSBsZWZ0IHN1YnRyZWUgPSBMIGFuZCBhIHJpZ2h0IHN1YnRyZWUgbnVtYmVyZWQgaGlnaGVyIHRoYW4gUi48XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgZmlyc3QgMTAgYmluYXJ5IHRyZWVzIGFuZCB0cmVlIG51bWJlciAyMCBpbiB0aGlzIHNlcXVlbmNlIGFyZSBzaG93biBiZWxvdzo8XC9wPlxyXG5cclxuPHByZT5cclxuICAgICAgICAwICAxICAyICAgICAgMyAgNCAgICAgIDUgICAgICA2ICAgICAgNyAgICAgIDggIDkgICAgICAgIC4uLiAgICAgMjBcclxuXHJcbiAgICAgICAgICAgWCAgWCAgICAgIFggIFggICAgICBYICAgICAgWCAgICAgIFggICAgICBYICBYICAgICAgICAgICAgICAgICBYXHJcbiAgICAgICAgICAgICAgIFxcICAgIFwvICAgIFxcICAgICAgXFwgICAgXC8gXFwgICAgXC8gICAgICBcLyAgICBcXCAgICAgICAgICAgICAgIFwvXHJcbiAgICAgICAgICAgICAgICBYICBYICAgICAgWCAgICAgIFggIFggICBYICBYICAgICAgWCAgICAgIFggICAgICAgICAgICAgWFxyXG4gICAgICAgICAgICAgICAgICAgICAgICAgICBcXCAgICBcLyAgICAgICAgICAgXFwgICAgXC8gICAgICAgIFxcICAgICAgICAgICBcLyBcXFxyXG4gICAgICAgICAgICAgICAgICAgICAgICAgICAgWCAgWCAgICAgICAgICAgICBYICBYICAgICAgICAgIFggICAgICAgICBYICAgWFxyXG4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBcXFxyXG4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgWFxyXG48XC9wcmU+XHJcblxyXG48cD5Zb3VyIGpvYiBmb3IgdGhpcyBwcm9ibGVtIGlzIHRvIG91dHB1dCBhIGJpbmFyeSB0cmVlIHdoZW4gZ2l2ZW4gaXRzIG9yZGVyIG51bWJlcjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgY29uc2lzdHMgb2YgbXVsdGlwbGUgcHJvYmxlbSBpbnN0YW5jZXMuIEVhY2ggaW5zdGFuY2UgY29uc2lzdHMgb2YgYSBzaW5nbGUgaW50ZWdlciBuLCB3aGVyZSAxJCBcXGxlJG4kIFxcbGUkNTAwLCAwMDAsIDAwMC4gQSB2YWx1ZSBvZiBuID0gMCB0ZXJtaW5hdGVzIGlucHV0LiAoTm90ZSB0aGF0IHRoaXMgbWVhbnMgeW91IHdpbGwgbmV2ZXIgaGF2ZSB0byBvdXRwdXQgdGhlIGVtcHR5IHRyZWUuKTxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBwcm9ibGVtIGluc3RhbmNlLCB5b3Ugc2hvdWxkIG91dHB1dCBvbmUgbGluZSBjb250YWluaW5nIHRoZSB0cmVlIGNvcnJlc3BvbmRpbmcgdG8gdGhlIG9yZGVyIG51bWJlciBmb3IgdGhhdCBpbnN0YW5jZS4gVG8gcHJpbnQgb3V0IHRoZSB0cmVlLCB1c2UgdGhlIGZvbGxvd2luZyBzY2hlbWU6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+QSB0cmVlIHdpdGggbm8gY2hpbGRyZW4gc2hvdWxkIGJlIG91dHB1dCBhcyBYLjxcL2xpPlxyXG5cdDxsaT5BIHRyZWUgd2l0aCBsZWZ0IGFuZCByaWdodCBzdWJ0cmVlcyBMIGFuZCBSIHNob3VsZCBiZSBvdXRwdXQgYXMgKEwmIzM5OylYKFImIzM5OyksIHdoZXJlIEwmIzM5OyBhbmQgUiYjMzk7IGFyZSB0aGUgcmVwcmVzZW50YXRpb25zIG9mIEwgYW5kIFIuXHJcblx0PHVsPlxyXG5cdFx0PGxpPklmIEwgaXMgZW1wdHksIGp1c3Qgb3V0cHV0IFgoUiYjMzk7KS5cclxuXHRcdDx1bD5cclxuXHRcdFx0PGxpPklmIFIgaXMgZW1wdHksIGp1c3Qgb3V0cHV0IChMJiMzOTspWC48XC9saT5cclxuXHRcdDxcL3VsPlxyXG5cdFx0PFwvbGk+XHJcblx0PFwvdWw+XHJcblx0PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=