Anthony and Cora

Anthony and Cora play a very exciting game. Initially, Anthony has $N$ points and Cora has $M$ points. The game then goes on for several rounds, during each round, either Anthony wins or Cora wins, the loser of the round loses $1$ point while nothing happens to the winner of the round. The game ends when either Anthony or Cora has no points left, and the one still left with points is the winner of the game.

Cora promises Anthony a sweet prize if he wins the game, but will cruelly humiliate Anthony if he loses. Anthony can very accurately evaluate himself and perfectly predict that his probability of winning the round $i$ is exactly $p_ i$. Now, in order to decide whether to play this game with Cora or not, he needs to know the probability of him winning the game.

Help Anthony find his probability of winning!


The first line contain integers $1\leq N,M\leq 1\, 000$. $N+M-1$ lines follow, with the $i$-th line containing $0\leq p_ i\leq 1$, $p_ i$ has at most $6$ decimal digits.


Output a single line containing the probability of Anthony winning this game. Your answer will be considered correct if its absolute or relative error doesn’t exceed $10^{-6}$.

Sample Input 1 Sample Output 1
1 1
Sample Input 2 Sample Output 2
3 2
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
Modan Han
Source Calgary Collegiate Programming Contest 2017
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in