ZOJ Problem Set - 1062 Trees Made to Order Python&n

#encoding=utf8

import sys

 
# h(n) n 
h = []
# s(n) n 
# s(n) = h(n-1) + s(n-1)
s = []
def print_tree(node_n, no):

    """ node_n no ，no 1 """
    index = 1
    for i in range(0, node_n):
        if no < index + h[i] * h[node_n - 1 - i]:
            no_right = (no - index + 1) % h[node_n - 1 - i]
            if no_right == 0:
                no_left = (no - index + 1) / h[node_n - 1 - i]
                no_right = h[node_n - 1 - i]
            else:
                no_left = (no - index + 1) / h[node_n - 1 - i] + 1
            #  
            if i > 0:
                sys.stdout.write('(')
                print_tree(i, no_left)
                sys.stdout.write(')')
            sys.stdout.write('X')

            #  
            if node_n - 1 - i > 0:
                sys.stdout.write('(')
                print_tree(node_n - 1 - i, no_right)
                sys.stdout.write(')')
            break
        else:
            index += h[i] * h[node_n - 1 - i]

            
if __name__ == '__main__':

    #  s[] h[] 
    h.append(1)
    h.append(1)
    s.append(0)
    s.append(1)
    #  s[] h[]
    while s[-1] < 500000000:
        n = len(h)
        h_n = 0
        for i in range(0, n):
            h_n += h[i] * h[n - 1 - i]
        h.append(h_n)
        s.append(s[-1] + h[len(s) - 1])

    for no in sys.stdin:
        no = int(no)
        if no == 0:
            break
        for i in reversed(range(0, len(s))):
            if no >= s[i]:
                # node_n 
                node_n = i
                print_tree(node_n, no - s[i] + 1)

        print ''