eolymp
bolt
Try our new interface for solving problems
Məsələlər

Нумерация деревьев

Нумерация деревьев

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Занумеруем все бинарные деревья согласно следующей схемы: - Пустое дерево имеет номер 0. - Дерево с единственной вершиной имеет номер 1. - Все бинарные деревья с m вершинами имеют номера, меньшие номеров деревьев с m + 1 вершиной. - Любое бинарное дерево с m вершинами, левое поддерево которого имеет номер L, а правое R, имеет номер n тогда и только тогда, когда все деревья с m вершинами у которых номер > n обладают одним из свойств: - левое поддерево имеет номер, больший L, или - левое поддерево имеет номер L, а правое поддерево имеет номер, больший R. Первые 10 бинарных деревьев и 20-ое дерево этой последовательности приведены ниже:

Вам требуется вывести бинарное дерево по его номеру.

Giriş verilənləri

Состоит из нескольких тестов. Каждый тест содержит одно целое число n (1n500,000,000). Последняя строка содержит n = 0 и не обрабатывается. (Заметьте, что таким образом у Вас никогда не будет выведено пустое дерево)

Çıxış verilənləri

Для каждого значения n следует вывести строку, содержащую дерево с номером n. Для вывода дерева воспользуйтесь следующей схемой:

Дерево без детей выводить как X. Дерево с левым поддеревом L и правым R следует выводить в виде (L')X(R'), где L' и R' - представления поддеревьев L и R. Если L пусто, то выводить X(R'). Если R пусто, то выводить (L')X.

Nümunə

Giriş verilənləri #1
1
20
31117532
0
Çıxış verilənləri #1
X
((X)X(X))X
(X(X(((X(X))X(X))X(X))))X(((X((X)X((X)X)))X)X)