Задачи
Нумерация деревьев
Нумерация деревьев
Занумеруем все бинарные деревья согласно следующей схемы: - Пустое дерево имеет номер \textbf{0}. - Дерево с единственной вершиной имеет номер \textbf{1}. - Все бинарные деревья с \textbf{m} вершинами имеют номера, меньшие номеров деревьев с \textbf{m + 1} вершиной. - Любое бинарное дерево с \textbf{m} вершинами, левое поддерево которого имеет номер \textbf{L}, а правое \textbf{R}, имеет номер \textbf{n} тогда и только тогда, когда все деревья с \textbf{m} вершинами у которых номер > \textbf{n} обладают одним из свойств: - левое поддерево имеет номер, больший \textbf{L}, или - левое поддерево имеет номер \textbf{L}, а правое поддерево имеет номер, больший \textbf{R}. Первые \textbf{10} бинарных деревьев и \textbf{20}-ое дерево этой последовательности приведены ниже:
\includegraphics{https://static.e-olymp.com/content/2f/2f4c46e3d8bdde45e5fc03a97dd362fa2e22fd61.jpg}
Вам требуется вывести бинарное дерево по его номеру.
\InputFile
Состоит из нескольких тестов. Каждый тест содержит одно целое число \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{500,000,000}). Последняя строка содержит \textbf{n} = \textbf{0} и не обрабатывается. (Заметьте, что таким образом у Вас никогда не будет выведено пустое дерево)
\OutputFile
Для каждого значения \textbf{n} следует вывести строку, содержащую дерево с номером \textbf{n}. Для вывода дерева воспользуйтесь следующей схемой:
Дерево без детей выводить как \textbf{X}. Дерево с левым поддеревом \textbf{L} и правым \textbf{R} следует выводить в виде \textbf{(L')X(R')}, где \textbf{L'} и \textbf{R'} - представления поддеревьев \textbf{L} и \textbf{R}. Если \textbf{L} пусто, то выводить \textbf{X(R')}. Если \textbf{R} пусто, то выводить \textbf{(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)