Ranking AVL trees P20941


Statement
 

pdf   zip

html

Given a non-empty binary tree T, let TL and TR denote respectively the left child of T and the right child of T. A binary tree T is an AVL tree if and only if T is empty, or TL and TR are AVL trees such that | height(TL) − height(TR) | ≤ 1. These are some examples of AVL trees with respective heights 0, 1, 2, 2, 2, 3 and 3 (a box denotes an empty tree):

We can inductively define a total order over AVL trees as follows: The empty tree is the smallest AVL tree. For every two non-empty AVL trees A and B, A < B if and only if

  • height(A) < height(B), or
  • height(A) = height(B) and AL < BL, or
  • height(A) = height(B) and AL = BL and AR < BR.

The trees in the picture above are the first, second, ... , seventh AVL trees using this order.

Write a program such that, for every given AVL tree, computes and prints its rank (that is, its position in the infinite sorted list of AVL trees, starting at 1).

Input

Input begins with the number of cases n, followed by n strings, each one with the preorder of an AVL tree, with ‘1’ denoting a node and ‘0’ denoting a leaf. No given tree has height larger than 6.

Output

For every given AVL tree, print its rank.

Public test cases
  • Input

    3
    100
    110010100
    11111100010011000111000100111100010011000
    

    Output

    2
    6
    6736354888
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Tercer Concurs de Programació de la UPC - Semifinal
    Date
    2005-09-14