Swedish coins (1) P95248


Statement
 

pdf   zip

thehtml

You have a collection C of n old Swedish coins. Every coin i has a probability pi of landing heads (and a probability 1 − pi of landing tails). Consider the following experiment for every subset S of C: Flip each coin in S exactly once, and count the number of heads; you win if this number is odd. Let w(S) denote the winning probability of the subset S.

Given two real numbers ℓ and r, and a collection of coins C, how many subsets S of C are such that ℓ < w(S) < r?

Input

Input consists of several cases. Every case begins with two real numbers ℓ and r, followed by n, followed by p1pn. Assume 0 < ℓ < r < 1, 1 ≤ n ≤ 40 and 0 < pi < 1.

Output

For every case, print the number of subsets S such that ℓ < w(S) < r. The input cases have no precision issues.

Observation

Please take into account that the result can be larger than 1012.

Public test cases
  • Input

    0.2 0.4
    1  0.3
    
    0.4 0.5
    1  0.3
    
    0.45 0.71
    2  0.7 0.6
    
    0.49 0.51
    5  0.5 0.5 0.5 0.5 0.5
    

    Output

    1
    0
    3
    31
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++