時間制限:1000ミリ秒
メモリ制限:10000KB
注文された木
問題
二分木を以下の方法で番号づけする:
空の木は0である。
1つの節点を持つ木は1である。
m個の節点を持つ木の番号はm+1個の節点を持つ木の番号より小さい。
m個の節点を持つ木2つを比べたとき、番号の大きいものは左側の木の番号が大きいか、左側の木の番号は同じで右側の木の番号が大きいかのどちらかである。
この番号づけにおける最初の10個の二分木と20番の木を以下に示す:
あなたの仕事は、与えられた番号に対応する木を出力することである。
入力
入力はいくつかのテストケースからなる。 各テストケースは木の番号をあらわす整数n(1 <= n <= 500,000,000)からなる。n=0が与えられたときは、空の木を出力する必要はなく、入力の終わりを意味する。
出力
各々のテストケースについて、nに対応する木を出力する必要がある。木を出力するために、以下の表現方法を用いること。
子のない木はXと出力される。
左右に子のある木は、右の木の表現R'と左の木の表現L'を用いて再帰的に(L')X(R')と出力される。
左が空なら、X(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)
出典
East Central North America 2001