H :: Candy Crush
Time Limit: 15 Seconds Memory Limit: 65536 KB
The King.com Ltd. best known for developing the Candy Crush game has decided to add an experimental interesting feature to Candy Crush in order to test its effectiveness to incentivize people to spend much more time playing the game. With this feature, a nice badge will be given to the player after winning each level, even those levels the player has already won. These badges fall under N different categories. After winning a level, the player will win a badge randomly from one of these categories. Once a player win at least one single badge from all categories, a special funny level is unlocked and the player will be rewarded a bunch of Lollipops and Color Bombs by winning this special level.
Mr. Sisaman who is a fan of Candy Crush wants to win the reward because he has got trapped in a very hard level that can’t be passed without using the Lollipops. But these days he is over busy working on a project so he has not much time to play Candy Crush. On the other hand, this experimental feature may be canceled after a while and he loses the chance of winning the reward.
After one day, Mr. Joachim - the blog moderator of Candy Crush - published a post on Candy Crush blog introducing this new feature. It was announced that a badge of category j, will appear with probability pj after winning a level. This information was meaningful for Mr. Sisaman because now he can find the number of levels he has to win to get the reward. But if he had time to calculate the expected number of levels, he would just play instead of doing calculation. So he turned to you to help him.
Input
First line of each test case starts with N, the number of badge categories. (N <= 10) The next line consists of N real numbers p1 to pN , the probability of winning a badge of category 1 to N, after winning a level. A value of N = 0 indicates end of input.
Output
For each test case, output a real number - the expected number of levels Mr. Sisaman needs to win to get the reward, rounded to four digits after decimal point.
Sample Input
2 0.5 0.5 3 0.2 0.3 0.5 0
Sample Output
3.0000 6.6548Submit
Source: 13th Iran Nationwide Internet Contest - Isfahan