Heads or tails P22482


Statement
 

pdf   zip

thehtml

Anna and Ivet toss coins. Anna will win the game after m heads, and Ivet will win after n ‍tails (whichever happens first). They have n coins, each with a probability pi of landing heads (and a probability 1 − pi of landing tails). They start tossing the first coin. Anna, who chose the rules, decided that the same coin will be used as long as it lands heads, and that after landing tails the next coin will be used. How likely will Anna win?

Input

Input consists of several cases, each with m, n and the n probabilities. You can suppose 1 ≤ m, n ≤ 1000.

Output

For every case, print the probability that Anna wins with 4 digits after the decimal point.

Public test cases
  • Input

    1 1   0.7
    2 1   0.7
    9 2   0 1
    9 1   0
    1 3   0.9 0.7 0.8
    4 3   0.9 0.7 0.8
    1000 3   0.9 0.7 0.8
    

    Output

    0.7000
    0.4900
    1.0000
    0.0000
    0.9940
    0.9255
    0.0000
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++