Нумерация деревьев
Занумеруем все бинарные деревья согласно следующей схемы: - Пустое дерево имеет номер 0. - Дерево с единственной вершиной имеет номер 1. - Все бинарные деревья с m вершинами имеют номера, меньшие номеров деревьев с m + 1 вершиной. - Любое бинарное дерево с m вершинами, левое поддерево которого имеет номер L, а правое R, имеет номер n тогда и только тогда, когда все деревья с m вершинами у которых номер > n обладают одним из свойств: - левое поддерево имеет номер, больший L, или - левое поддерево имеет номер L, а правое поддерево имеет номер, больший R. Первые 10 бинарных деревьев и 20-ое дерево этой последовательности приведены ниже:
Вам требуется вывести бинарное дерево по его номеру.
Входные данные
Состоит из нескольких тестов. Каждый тест содержит одно целое число n (1 ≤ n ≤ 500,000,000). Последняя строка содержит n = 0 и не обрабатывается. (Заметьте, что таким образом у Вас никогда не будет выведено пустое дерево)
Выходные данные
Для каждого значения n следует вывести строку, содержащую дерево с номером n. Для вывода дерева воспользуйтесь следующей схемой:
Дерево без детей выводить как X. Дерево с левым поддеревом L и правым R следует выводить в виде (L')X(R'), где L' и R' - представления поддеревьев L и R. Если L пусто, то выводить X(R'). Если R пусто, то выводить (L')X.