<PREV Problem:
NEXT>
Solved by 1293 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

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.

SAMPLE INPUT:
(((3 5) 1) (9 4))
SAMPLE OUTPUT:
4.50

Athor:
Voroztsov Artem

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


© acm.mipt DevGroup
The page was generated in 210ms

SW soft NIX
ID = 54.161.108.158