Educational DP Contest AtCoder I - Coins

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 1G

Problem types

Let N be a positive odd number.

There are N coins, numbered 1, 2, \dots, N. For each i (1 \le i \le N), when Coin i is tossed, it comes up heads with probability p_i and tails with probability 1 - p_i.

Taro has tossed all the N coins. Find the probability of having more heads than tails.

Constraints

  • N is an odd number.
  • 1 \le N \le 2999.
  • p_i is a real number and has two decimal places.
  • 0 < p_i < 1

Input Specification

The first line will contain the integer N.

The next line will contain N floats, p_1, p_2, \dots, p_N.

Output Specification

Print the probability of having more heads than tails. The output is considered correct when the absolute error is not greater than 10^{-9}.

Sample Input 1

3
0.30 0.60 0.80

Sample Output 1

0.612

Explanation For Sample 1

The probability of each case where we have more heads than tails is as follows:

  • The probability of having (Coin1, Coin2, Coin3) = (Head,Head,Head) is 0.3 \times 0.6 \times 0.8 = 0.144;
  • The probability of having (Coin1, Coin2, Coin3) = (Tail,Head,Head) is 0.7 \times 0.6 \times 0.8 = 0.336;
  • The probability of having (Coin1, Coin2, Coin3) = (Head,Tail,Head) is 0.3 \times 0.4 \times 0.8 = 0.096;
  • The probability of having (Coin1, Coin2, Coin3) = (Head,Head,Tail) is 0.3 \times 0.6 \times 0.2 = 0.036;

Thus, the probability of having more heads than tails is 0.144 + 0.336 + 0.096 + 0.036 = 0.612.

Sample Input 2

1
0.50

Sample Output 2

0.5

Explanation For Sample 2

Outputs such as 0.500, 0.500000001 and 0.499999999 are also considered correct.

Sample Input 3

5
0.42 0.01 0.42 0.99 0.42

Sample Output 3

0.3821815872

Comments


  • 9
    discoverMe  commented on March 28, 2019, 3:17 p.m.

    remember that doubles are automatically rounded to 6 decimal places during output