<PREV Problem:
NEXT>
Solved by 41 users: fetetriste, svirg, vi002, HeaDacHe, WsemirZ, zloy_mipt, rvashegin, JohnJones_001, FordPerfect, Cheryl, arti, Chmeli_BSU, lutyj, ignat, tourist, pmnox, tomek, mazahaka, UdH-WiNGeR, Philip_PV, defrager, RAVEman, knightry, wangyc, Jacob, daniel.ugra, DAV, Dest, mathematic, DD, Kuznetsov_S, ripatti, vitar, mkirsche, Fat, Bryak211, akk, checkil, NIGHTFIT, avg79, ilia.
UserDateAttemptTimeCMSC
DAV16 mar 2010C++501.08176 
Jacob30 jun 2009C++901.33192 
Philip_PV18 feb 2009C++201.96195 
rvashegin11 jun 2008C++601.65197 
ripatti05 may 2011C++902.00200 
lutyj11 aug 2008C++101.41205 
Philip_PV18 feb 2009C++101.45206 
fetetriste31 may 2008C++101.11214 
RAVEman27 feb 2009C++201.15214 
Fat24 feb 2012C++1201.16215 
Chmeli_BSU04 aug 2008C++101.42215 
Languages
C++
37
C
2
Kylix
1
FPC
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

Taxi 5

Time limit = 2 second(s)

Memory limit = 4000

Taxi driver Daniel likes to tell funny jokes to his passengers. He thinks that his duty is to tell two funny jokes to each passenger. But if a passenger doesn't laugh at а joke, he concludes that the joke is not so funny and then he will never tell this joke.

Daniel knows N funny jokes. He knows the funnitude of each joke — the probability of the event that a randomly choosed passenger will laugh at this joke.

Daniel can't invent new jokes. And when less than two jokes remain, he gives up driving. But he loves driving. Therefore he tells the jokes in that order to maximize the expected number of runs.

You task is to determine the expected number of runs.

Input The first line contains an integer number N, 0 ≤ N ≤ 10000. The second line contains N numbers pi — the funnitudes of the jokes, 0 ≤ pi ≤ 0.9999.

Output One number — expected value of the number of runs. The relative error mustn't be greater than 10-9.

Input#1
2
0.5 0.5
Output#1
1.33333333333333

Input#2
5
0.8 0.8 0.9 0.9 0.8
Output#2
14.5876548893019

Author:
Alexander Potashev, thanks to Eugene Barsky for the algorithmic idea.
24 May 2008

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


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

SW soft NIX
ID = 3.234.244.18