<PREV Problem:
NEXT>
Solved by 1293 users: ...
UserDateAttemptTimeCMSC
xtender11 apr 2010Perl2900.064 
sb3ar23 dec 2007Ruby1600.0219 
sb3ar23 dec 2007Ruby1700.0219 
xtender11 apr 2010Perl2700.0519 
sb3ar11 dec 2007Ruby1500.0223 
xtender11 apr 2010Perl2400.0524 
Nakilon13 jan 2010Ruby1200.0231 
Nakilon13 jan 2010Ruby1400.0231 
Nakilon11 apr 2010Ruby1600.0231 
Nakilon13 jan 2010Ruby1300.0232 
Nakilon12 apr 2010Ruby1800.0232 
fetetriste24 apr 2007Ruby900.0235 
fetetriste24 apr 2007Ruby800.0242 
lacrosse20 sep 2013Ruby500.0246 
borodiy_11112 sep 2011Scheme100.2646 
var24 apr 2007Ruby400.0247 
fetetriste24 apr 2007Ruby700.0248 
pauc29 dec 2011Perl200.0448 
Rocker28 dec 2007Ruby200.0249 
harya_krishnii13 oct 2009Ruby200.0249 
var24 apr 2007Ruby300.0249 
Languages
C++
617
C
269
FPC
248
Java
68
Kylix
48
Ruby
29
Python
17
Perl
9
Scheme
6
Haskell
2
Lua
2
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

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 190ms

SW soft NIX
ID = 18.208.202.194