|Online MIPT programming contest||РУССКИЙ|
Time limit = 2 second(s)
Memory limit = 4000Taxi 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.
2 0.5 0.5
5 0.8 0.8 0.9 0.9 0.8
Alexander Potashev, thanks to Eugene Barsky for the algorithmic idea.
24 May 2008
© acm.mipt DevGroup
The page was generated in 210ms