Planet Cake P12956


Statement
 

pdf   zip

thehtml

In the planet Cake, home of the Master Masao, a casino offers a particular game. There is an array of probabilities p1, …, p2m+1 for some natural number m. At every moment, a coin has probability pi of landing heads when flipped. If it indeed lands heads, the next time the probability will be pi+1. Otherwise, the probability will be pi−1. The initial “state” is m+1. Before playing, you must decide a number k between 1 and m+1. Afterwards, you flip the coin k times. You win if the total number of times the coin landed heads is an odd number.

Given the probabilities of a coin, compute the probability of winning a game assuming an optimal strategy.

Input

Input consists of several cases, each with an odd number n followed by n ‍probabilities. Assume n < 50.

Output

For every case, print the probability of winning with four digits after the decimal point. The input cases have no precision issues.

Public test cases

  • Input

    1   0.7
3   1 1 0
3   0.5 0.5 0.5
11  0.4 0.5 0.6 0.7 0.8
    0.9 1 0 0.1 0.2 0.3
3   0.8 0.6 0.3

    Output

    0.7000
1.0000
0.5000
0.9914
0.7400
    • Information
    Author
    Xavier Martínez
    Language
    English
    Official solutions
    C++
    User solutions
    C++