Planet Cake P12956


Statement
 

pdf   zip

html

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++
    Event
    Setè Concurs de Programacio de la UPC - Semifinal
    Date
    2009-06-29