Random descending a tree

Time limit: 5 seconds

Input contains a description of a binary tree, every leaf of which has an integer number from the range -10^6 ... 10^6. Starting from the root, one randomly descends the tree, choosing left or right subtrees at each inner vertex with equal probabilities.

Find the expectation value of the number that we encounter after reaching a leaf. Output the answer with two decimal digits. The description of the tree is given in the following format:

	    
    tree ::= leaf | (tree tree);
    leaf ::= integer;

For example,

(((3 5) 1) (9 4))

The number of vertices of the tree is less than 1000.

(((3 5) 1) (9 4))

4.50

Athor:
Voroztsov Artem

<PREV | Problem set | Search related messages | NEXT>