Problem:
 Score : 100 points    Problem Statement Let N be a positive odd number.  There are N coins, numbered 1, 2, \ldots, N .
For each i ( 1 \leq i \leq 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 \leq N \leq 2999  p_i is a real number and has two decimal places.  0 < p_i < 1         Input Input is given from Standard Input in the following format:  N  p_1  p_2  \ldots  p_N       Output 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  The probability of each case where we have more heads than tails is as follows:   The probability of having (Coin 1, Coin 2, Coin 3) = (Head, Head, Head) is 0.3 × 0.6 × 0.8 = 0.144 ;  The probability of having (Coin 1, Coin 2, Coin 3) = (Tail, Head, Head) is 0.7 × 0.6 × 0.8 = 0.336 ;  The probability of having (Coin 1, Coin 2, Coin 3) = (Head, Tail, Head) is 0.3 × 0.4 × 0.8 = 0.096 ;  The probability of having (Coin 1, Coin 2, Coin 3) = (Head, Head, Tail) is 0.3 × 0.6 × 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  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

Solution (Python):


from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  


def debug(*x):
    print(*x)


def solve(N, probs):
    "void()"
    m = [0.0] * (N + 1)
    m[0] = 1.0

    for i in range(N):
        n = [0.0] * (N + 1)
        for j in range(N):
            n[j + 1] += m[j] * probs[i]
        for j in range(N + 1):
            n[j] += m[j] * (1 - probs[i])
        m = n
    return sum(m[N // 2 + 1:])


def main():
    N = int(input())
    probs = list(map(float, input().split()))
    print(solve(N, probs))


T1 = """
3
0.30 0.60 0.80
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    0.612
    """


T3 = """
5
0.42 0.01 0.42 0.99 0.42
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    0.3821815872
    """


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        
        
        from my_module import solve  
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Solution (Python):
n=int(input())
p=list(map(float,input().split()))
dp=[[0 for _ in range(n+1)]for _ in range(n)]
dp[0][0]=1-p[0]
dp[0][1]=p[0]
for i in range(1,n):
  for j in range(i+2):
    dp[i][j]=dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i])
print(sum(dp[-1][(n+1)//2:]))

Solution (Python):
N = int(input())
p = list(map(float, input().split()))
dp = [[0.0 for i in range(N+1)] for j in range(N+1)]
dp[0][0] = 1.0
for i in range(N):
    for j in range(N):
        dp[i+1][j+1] += dp[i][j] * p[i]
        dp[i+1][j] += dp[i][j] * (1 - p[i])
temp = (N+1) // 2
ans = 0
for i in range(temp, N+1):
    ans += dp[N][i]
print(ans)

Solution (Python):
n = int(input())
p = list(map(float, input().split()))

dp = [[0 for i in range(n+1)] for j in range(n+1)]
dp[0][0] = 1

for i in range(n):
    for j in range(n):
        dp[i+1][j+1] += dp[i][j]*p[i]
        dp[i+1][j] += dp[i][j]*(1-p[i])

ans = 0
for i in range(n+1):
    if i > n-i:
        ans += dp[n][i]

print(ans)

Solution (Python):
n = int(input())
p = [float(i) for i in input().split()]

dp = [[0 for i in range(n+1)] for j in range(n+1)]
dp[0][0] = 1

for i in range(n):
    for j in range(n+1):
        if not j:
            dp[i+1][j] = dp[i][j]*(1-p[i])
        else:
            dp[i+1][j] = dp[i][j]*(1-p[i]) + dp[i][j-1]*p[i]

print(sum(dp[n][((n+1)//2):]))

Solution (Python):
n = int(input())

heads = list(map(float, input().split()))

dp = []

for i in range(n+1):
    temp = []
    for j in range(n+1):
        temp.append(0.0)
    
    dp.append(temp)

dp[0][0] = 1.0

for i in range(1, n+1):
    for j in range(0, n+1):
        dp[i][j] = dp[i-1][j] * (1-heads[i-1]) + dp[i-1][j-1] * heads[i-1]


ans = 0
for i in range((n+1)//2, n+1):
    ans += dp[n][i]

print(ans)

Solution (Python):
N = int(input())
p = list(map(float, input().split()))

dp = [[0.0] * (N + 1) for _ in range(N + 1)]
dp[1][0] = 1 - p[0]
dp[1][1] = p[0]
for i in range(2, N + 1):
    for j in range(N + 1):
        if j == 0:
            dp[i][j] = dp[i - 1][j] * (1 - p[i - 1])
        else:
            dp[i][j] = dp[i - 1][j] * (1 - p[i - 1]) + dp[i - 1][j - 1] * p[i - 1]
M = N // 2 + 1
ans = 0
for i in range(M, N + 1):
    ans += dp[-1][i]
print(ans)

Solution (Python):
import numpy as np

n = int(input())
p = list(map(float, input().split()))

dp = np.zeros(n + 1, float)
dp[0] = 1
for e in p:
    dp[1:] += dp[:-1] * e / (1 - e)
    dp *= 1 - e

ans = dp[(n+1)//2:].sum()
print(ans)

Solution (Python):
import math

n = int(input())
lst = list(map(float, input().split()))

dp = [[0] * (n+1) for _ in range(n+1)] 
dp[0][0] = 1
for i in range(0, n):
    for j in range(0, n):
        dp[i+1][j+1] += dp[i][j] * lst[i] 
        dp[i+1][j] += dp[i][j] * (1 - lst[i]) 
        
hlf = math.ceil(n/2)
ansl = dp[n][hlf:n+1]
ans = sum(ansl)
print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



n = int(input())
p = list(map(float, input().split()))
dp = [[0]*(n+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
    for j in range(i+1):
        dp[i][j] = dp[i-1][j] * (1-p[i-1]) + dp[i-1][j-1] * p[i-1]
print(sum(dp[n][j] for j in range(n//2+1, n+1)))

Solution (Python):
N = int(input())
p = list(map(float, input().split()))

import numpy as np
dp = np.zeros(N+1)
dp[0] = 1

for i in range(N):
    dp[1:] = dp[1:]*(1-p[i]) + dp[:-1]*p[i]
    dp[0] *= (1-p[i])

print(sum(dp[int(N/2)+1:] ))

Solution (Python):


import numpy as np

LI = lambda: list(map(float, input().split()))


N = int(input())
P = LI()


def main():
    dp = np.zeros((N + 1, N + 1))
    dp[0][0] = 1
    for i in range(1, N + 1):
        p = P[i - 1]
        bac = dp[i - 1][:i] * (1 - p)
        hos = dp[i - 1][:i] * p
        dp[i][:i] += bac
        dp[i][1 : i + 1] += hos
    ans = sum(dp[N][(N + 1) // 2:])
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys;
import math;
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def get_array(): return list(map(float, sys.stdin.readline().strip().split()))
def get_string(): return sys.stdin.readline().strip()

n = int(input());
arr = get_array();
dp = [[0 for i in range(n+1)] for i in range(n+1)];
dp[0][0]=1;
for i in range(1,n+1):
    dp[i][0]=dp[i-1][0]*(1-arr[i-1])
for i in range(1,n+1):
    for j in range(1,n+1):
        if(i==j):
            dp[i][j]=dp[i-1][j-1]*arr[i-1];
            continue
        if(j>i):
            continue;
        dp[i][j] = dp[i-1][j-1]*arr[i-1]+dp[i-1][j]*(1-arr[i-1]);

ans = 0;
for i in range(n+1):
    if(i>=n//2 + 1):
        ans += dp[n][i];
print(ans);

Solution (Python):
import numpy
N = int(input())
p = [i for i in map(float, input().split())]
memo = numpy.zeros([N+1, N+1], dtype = float)
memo[0][0] = 1
for n in range(N):
    memo[n+1] = memo[n]*(1-p[n])
    memo[n+1][1:N+1] += memo[n][0:N] * (p[n])
print(numpy.sum(memo[N][N//2+1:N+1]))

Solution (Python):
n = int(input())
arr = list(map(float, input().split()))

dp = [[0.0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1.0

for i in range(n):
    for j in range(i + 1):
        dp[i + 1][j + 1] += dp[i][j] * arr[i]
        dp[i + 1][j] += dp[i][j] * (1 - arr[i])

dp = dp[-1]

print(sum(dp[-(n + 1) // 2:]))

Solution (Python):
n = int(input())
p = list(map(float, input().split()))

dp = [[0 for _ in range(n+1)] for _ in range(n+1)]

dp[0][0] = 1.0 


for i in range(n):
    for j in range(n):
        dp[i+1][j+1] += dp[i][j] * p[i]
        dp[i+1][j] += dp[i][j] * (1-p[i])


ans = 1.0
for i in range((n+1)//2):
    ans -= dp[n][i]

print(ans)

Solution (Python):
def solve():
    N = int(input())
    Ps = list(map(float, input().split()))

    Qs = [1-P for P in Ps]

    dp = [0.0] * (N+2)
    dp[0] = 1.0
    for i, (P, Q) in enumerate(zip(Ps, Qs)):
        dp2 = [0.0] * (N+2)
        for j in range(i+1):
            dp2[j] += dp[j] * Q
            dp2[j+1] += dp[j] * P
        dp = dp2

    print(sum(dp[(N+1)//2:]))


solve()

Solution (Python):
def solve():
    N = int(input())
    Ps = list(map(float, input().split()))

    Qs = [1-P for P in Ps]

    dp = [0.0] * (N+2)
    dp[0] = 1.0
    for P, Q in zip(Ps, Qs):
        dp2 = [0.0] * (N+2)
        for j in range(N+1):
            if dp[j] == 0.0: continue
            dp2[j] += dp[j] * Q
            dp2[j+1] += dp[j] * P
        dp = dp2

    print(sum(dp[(N+1)//2:]))


solve()

Solution (Python):
n = int(input())
arr = list(map(float,input().split()))

dp=[]
for i in range(n+1):
    dp.append([0]*(n+1))
dp[1][0]=(1-arr[0])
dp[1][1]=arr[0]

for i in range(2,n+1):
    for j in range(0,i+1):
        dp[i][j]= dp[i-1][j-1]*arr[i-1] + dp[i-1][j]*(1-arr[i-1])
ans=0
for i in range(n//2+1,n+1):
    ans+=dp[n][i]

print(ans)

Solution (Python):
N = int(input())
p = [i for i in map(float, input().split(" "))]

dp = [[0] * (N+1) for _ in range(N+1)]
dp[0][0] = 1.0
for i in range(N):
    for j in range(i+1):
        dp[i+1][j+1] += dp[i][j] * p[i]
        dp[i+1][j] += dp[i][j] * (1.0-p[i])

res = 0.0
for i in range(N//2+1, N+1):
    res += dp[N][i]
print("{:.10f}".format(res))

Solution (Python):



def main():
    N = int(input())
    P = list(map(float, input().split()))

    dp = [0.0]*(N//2+2)
    dp[0] = 1.0
    for i in range(N):
        dp_ = [0.0]*(N+1)
        dp_[N//2+1]=dp[N//2+1]
        for j in range(min(i+1,N//2+1),-1,-1):
            dp_[j]+=dp[j-1]*P[i]
            dp_[j-1]+=dp[j-1]*(1-P[i])
        dp=dp_.copy()
    print(dp[N//2+1])

if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
p=[0]
p+=list(map(float,input().split()))

dp=[[0]*(n+1) for _ in range(n+1)]
dp[0][0]=1
for k in range(1,n+1):
    dp[0][k]=0
for i in range(1,n+1):
    for j in range(0,i+1):
        if j!=0:
            dp[i][j]=dp[i-1][j-1]*p[i]
        dp[i][j]+=dp[i-1][j]*(1-p[i])

res=0
for x in range((n+1)//2,n+1):
    res+=dp[n][x]
print(res)

Solution (Python):
n = int(input())
prob = list(map(float, input().split()))


dp = [[0 for i in range(n+1)] for j in range(n+1)]

dp[0][0] = 1.0

for i in range(1, n+1):
    for j in range(n+1):
        if j == 0:
            dp[i][j] = dp[i-1][j] * (1.0 - prob[i-1])
        else:
            dp[i][j] = prob[i-1] * dp[i-1][j-1] + (1.0 - prob[i-1]) * dp[i-1][j]

ans = 0
for i in range(n//2+1, n+1):
    ans += dp[n][i]

print(ans)

Solution (Python):
n=int(input())
p=list(map(float, input().split()))
       
dp=[[0 for i in range(n+1)] for j in range(n+1)]
dp[0][0]=1

for i in range(1,n+1):
       for j in range(n+1):
       	if j==0:
       		dp[i][j]=(1.0-p[i-1])*dp[i-1][j]
       	else:
       		dp[i][j]=p[i-1]*dp[i-1][j-1]+(1.0-p[i-1])*dp[i-1][j]
res=0
for i in range(n//2+1,n+1):
       res+=dp[n][i]
print(res)

Solution (Python):
import numpy as np
N = int(input())
P = list(map(float, input().split()))
dp = np.zeros((N+1,N+1),dtype=float)
dp[0,0] = 1

for i in range(N):
    dp[i+1] += dp[i] * (1-P[i])
    dp[i+1][1:] += dp[i][:-1] * P[i]
print(sum(dp[N, N//2+1:]))

Solution (Python):
n = int(input())
p = [float(i) for i in input().split()]

dp = [[0] * i for i in range(2,n+2)]

dp[0][1] = p[0]
dp[0][0] = 1-p[0]
ans = 0
if n != 1:
    for i in range(1,n):
        for j in range(len(dp[i])-1):
            
            dp[i][j] += dp[i-1][j] * (1-p[i])
            
            dp[i][j+1] += dp[i-1][j] * p[i]
    for i in range(1,(n+1)//2+1):
        ans += dp[n-1][-i]
    print(ans)
else:
    print(p[0])

Solution (Python):
N = int(input())
p = list(map(float, input().split()))


dp = [[0]*(N+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(1, N+1):
    for j in range(N+1):
        dp[i][j] += (1-p[i-1])*dp[i-1][j]
        if j >= 1:
            dp[i][j] += p[i-1]*dp[i-1][j-1]

print(sum([dp[N][N-j] for j in range((N+1)//2)]))

Solution (Python):
N = int(input())
p = list(map(float, input().split()))


dp = [[0]*(N+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(1, N+1):
    for j in range(N+1):
        dp[i][j] += (1-p[i-1])*dp[i-1][j]
        if j >= 1:
            dp[i][j] += p[i-1]*dp[i-1][j-1]

print(sum([dp[N][j] for j in range((N+1)//2, N+1)]))

Solution (Python):
def main():
    n = int(input())
    P = [0, ] + list(map(float, input().split()))
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(1, n + 1):
        for j in range(i + 1):
            dp[i][j] = dp[i - 1][j] * (1 - P[i]) + dp[i - 1][j - 1] * P[i]
    print(sum(dp[n][n // 2 + 1:]))


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
import sys
buf = sys.stdin.buffer

N = int(input())
M = N // 2 + 1
P = np.array(input().split(),dtype = float)

dp = np.zeros([(N + 1),(N + 1)])
dp[0][0] = 1.0

for i in range(N):
  tmp = dp[i].copy()
  dp[i + 1] = tmp * (1 - P[i])
  tmp = np.roll(tmp,1)
  dp[i + 1] += tmp * P[i] 
  
print(sum(dp[-1][M:]))

Solution (Python):
import numpy as np
import sys
buf = sys.stdin.buffer

N = int(buf.readline())
M = N // 2 + 1
P = np.array(buf.readline().split(),dtype = float)

dp = np.zeros([(N + 1),(N + 1)])
dp[0][0] = 1.0

for i in range(N):
  tmp = dp[i].copy()
  dp[i + 1] = tmp * (1 - P[i])
  tmp = np.roll(tmp,1)
  dp[i + 1] += tmp * P[i] 
  
print(sum(dp[-1][M:]))

Solution (Python):
from collections import defaultdict
N = int(input())
P = list(map(float, input().split()))

dp = defaultdict(float)
dp[(0, 0)] = 1.0

for p in P:
    newDP = defaultdict(float)
    for (X, Y), val in dp.items():
        
        newDP[(X + 1, Y)] += val * p
        
        newDP[(X, Y + 1)] += val * (1 - p)
    dp = newDP

ans = 0.0
for x in range(N + 1):
    y = N - x
    if x > y:
        ans += dp[(x, y)]

print(ans)

Solution (Python):
N = int(input())
P = list(map(float, input().split()))
dp = [[0]*(N+1) for _ in range(N)]
dp[0][0] = 1-P[0]
dp[0][1] = P[0]
for i in range(N):
    for k in range(N+1):
        if i-1 >= 0:
            dp[i][k] += dp[i-1][k]*(1-P[i])
            if k-1 >= 0:
                dp[i][k] += dp[i-1][k-1]*P[i]
ans = 0
for i in range(N+1):
    if i >= (-(-N//2)):
        ans += dp[-1][i]
print(ans)

Solution (Python):
def main():
    N = int(input())
    assert N % 2 == 1
    M = (N + 1) // 2
    P = list(map(float, input().split(' ')))
    dp = [[0 for _ in range(M + 1)] for _ in range(N)]
    dp[0][0] = 1 - P[0]
    dp[0][1] = P[0]
    for n in range(1, N):
        p = P[n]
        for m in range(min([n + 1, M]) + 1):
            if 1 <= m < M:
                dp[n][m] = dp[n - 1][m] * (1 - p) + dp[n - 1][m - 1] * p
            elif m == M:
                dp[n][m] = dp[n - 1][m] + dp[n - 1][m - 1] * p
            else:
                
                dp[n][m] = dp[n - 1][m] * (1 - p)
    print(dp[-1][-1])


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
plist = list(map(float, input().split()))
dp = [[0 for i in range(N+1)] for j in range(N)]
dp[0][0], dp[0][1] = plist[0], 1-plist[0]
for i in range(1, N):
    p = plist[i]
    for j in range(i+1):
        dp[i][j] += dp[i-1][j]*p
        dp[i][j+1] += dp[i-1][j]*(1-p)
print(sum(dp[-1][0:(N+1)//2]))

Solution (Python):
n=int(input())
li=[float(k) for k in input().split()]
dp=[[0 for i in range(len(li)+1)] for j in range(len(li)+1)] 
x=len(li)
dp[0][0]=1
for a in range(1,x+1):
  ph=li[a-1]
  pt=1-li[a-1]
  dp[a][0]=pt*dp[a-1][0]
  
  for b in range(1,a+1):
    dp[a][b]=dp[a-1][b-1]*ph+pt*dp[a-1][b]
ans=0
for i in range(x//2+1,x+1):
  ans=ans+dp[x][i]
print(ans)

Solution (Python):
n=int(input())
l=input().split()
li=[float(i) for i in l]

dp=[[0 for i in range(n+1)] for j in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
	dp[i][0]=dp[i-1][0]*(1-li[i-1])
for j in range(1,n+1):
	dp[0][j]=0
for i in range(1,n+1):
	for j in range(1,i+1):
		dp[i][j]=(dp[i-1][j-1]*li[i-1])+dp[i-1][j]*(1-li[i-1])
prob=0
for j in range(n+1):
	if(j>n/2):
		prob+=dp[n][j]
print(prob)

Solution (Python):


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def read_floats():
    return list(map(float, input().strip().split(' ')))


def solve():
    """
    OPT[N][M] - from N coins having exactly M head
    OPT[N][M] = OPT[N-1][M]*(1-P[N])+OPT[N-1][M-1]*P[N]

    OPT[0][0] = 1
    OPT[i][0] = P[i]
    """
    N = read_int()
    P = read_floats()
    OPT = [
        [0]*(N+1) for _ in range(N+1)
    ]
    OPT[0][0] = 1
    for i in range(1, N+1):
        for j in range(N+1):
            OPT[i][j] = OPT[i-1][j]*(1-P[i-1])
            if j > 0:
                OPT[i][j] += OPT[i-1][j-1]*P[i-1]
    return sum(OPT[-1][(N+1)//2:])


if __name__ == '__main__':
    print(solve())

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    P = list(map(float, input().split()))

    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1.0

    for i in range(1, n + 1):
        for j in range(1, i + 1):
            dp[i][j] += dp[i - 1][j - 1] * P[i - 1]
            dp[i][j - 1] += dp[i - 1][j - 1] * (1.0 - P[i - 1])

    res = 0
    for i in range(n // 2 + 1, n + 1):
        res += dp[-1][i]

    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
N = int(input())
P = list(map(float,input().split()))

dp = [[0]*(N+1) for _ in range(N+1)]

dp[0][0] = 1.0

for i in range(N):
    t = P[i]
    for j in range(i+1):
        dp[i+1][j+1] += dp[i][j]*t
    t = 1-P[i]
    for j in range(i+1):
        dp[i+1][j] += dp[i][j]*t

ans = sum(dp[N][N//2+1:])
print(ans)

Solution (Python):
N = int(input())
A = list(map(float, input().split()))


dp = [[0]*(N+1) for _ in range(N+1)]
dp[0][0] = 1

for i in range(1, N+1):
    for j in range(i+1):
        if j-1 >= 0:
            dp[i][j] = dp[i-1][j-1]*A[i-1] + dp[i-1][j]*(1 - A[i-1])
        else:
            dp[i][j] = dp[i-1][j]*(1 - A[i-1])

print(sum([dp[N][i] for i in range(N//2+1, N+1)]))

Solution (Python):
N = int(input())
plist = list(map(float, input().split()))
dp = [[0 for i in range(N+1)] for j in range(N)]
dp[0][0], dp[0][1] = plist[0], 1-plist[0]
for i in range(1, N):
    p = plist[i]
    for j in range(i+1):
        dp[i][j] += dp[i-1][j]*p
        dp[i][j+1] += dp[i-1][j]*(1-p)
print(sum(dp[-1][0:(N+1)//2]))

Solution (Python):
n = int(input())
dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
plist = list(map(float, input().split()))
dp[1][0], dp[1][1] = 1 - plist[0], plist[0]
for i in range(1, n):
    p = plist[i]
    for j in range(i + 1):
        dp[i + 1][j] += dp[i][j] * (1 - p)
        dp[i + 1][j + 1] += dp[i][j] * p
print(sum(dp[-1][n // 2 + 1:]))

Solution (Python):
import sys
input=sys.stdin.readline

n=int(input())


p=list(map(float,(input().split())))
dp=[[0]*(n+1) for i in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
	for j in range(n+1):
		if j==0:dp[i][j]=(1-p[i-1])*dp[i-1][j]
		else:dp[i][j]=p[i-1]*dp[i-1][j-1]+(1-p[i-1])*dp[i-1][j]
ans=0
for i in range(n//2+1,n+1):
	ans+=dp[n][i]
print(ans)

Solution (Python):
N = int(input())
p = list(map(float, input().split()))

dp = [[0]*(N+1) for _ in range(N+1)]
dp[0][0] = 1 

for i in range(1, N+1):
  for j in range(0, N+1):
    if j - 1 < 0:
      dp[i][j] = dp[i-1][j]*(1-p[i-1])
    else:
      dp[i][j] = (dp[i-1][j-1]*p[i-1]) + (dp[i-1][j]*(1-p[i-1]))

if N % 2==0:
  ans = sum(dp[N][int(N/2):])
else:
  ans = sum(dp[N][int(N//2)+1:])

print(ans)

Solution (Python):


def main():
    N = int(input())
    p = list(map(float, input().split()))
    dp = [[0.0] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 1.0
    for i in range(1, N+1):
        for j in range(0, N+1):
            dp[i][j] = dp[i - 1][j] * \
                (1 - p[i - 1]) + dp[i - 1][j - 1] * p[i - 1]
    print(sum(dp[N][N//2+1:]))


if __name__ == "__main__":
    main()

Solution (Python):


def main():
    N = int(input())
    p = list(map(float, input().split()))
    dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(1, N+1):
        for j in range(0, N+1):
            dp[i][j] = dp[i - 1][j] * \
                (1 - p[i - 1]) + dp[i - 1][j - 1] * p[i - 1]
    print(sum(dp[N][N//2+1:]))


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    N = int(input())
    p = list(map(float, input().split()))
    dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
    p_mul = 1
    dp[0][0] = 1
    for i in range(1, N + 1):
        p_mul *= (1-p[i-1])
        dp[i][0] = p_mul
    for i in range(1, N+1):
        for j in range(1, N+1):
            dp[i][j] = dp[i - 1][j] * \
                (1 - p[i - 1]) + dp[i - 1][j - 1] * p[i - 1]
    print(sum(dp[N][N//2+1:]))


if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter
from collections import deque
import math
import bisect
import sys
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
p=list(map(float,input().split()))
dp=[[0]*(n+1) for i in range(n+1)]
dp[0][0]=1
for i in range(n):
    for k in range(n):
        dp[i+1][k]+=dp[i][k]*(1-p[i])
        dp[i+1][k+1]+=dp[i][k]*p[i]
print(sum(dp[n][n//2+1:]))

Solution (Python):
n = int(input())
p = list(map(float,input().split()))
dp = [[0] * (n + 1) for i in range(n)]

for i in range(n):
    for j in range(n):
        if i == 0:
            dp[0][0] = 1 - p[0]
            dp[0][1] = p[0]

        else:
            
            dp[i][j] += dp[i - 1][j] * (1 - p[i])
            if dp[i - 1][j] == 0:continue
            
            dp[i][j + 1] += dp[i - 1][j] * p[i]
print(sum(dp[-1][n//2 + 1:]))

Solution (Python):
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]

def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]

def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)

MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N = I()
P = list(map(float,input().split()))
dp = FILL2(0,N+3,N+3)
dp[0][0] = 1
for i in range(N):
    for j in range(N):
        dp[i+1][j+1] += dp[i][j]*P[i]
        dp[i+1][j] += dp[i][j]*(1-P[i])
print(sum(dp[N][N//2+1:]))

Solution (Python):
N=int(input())
P= list(map(float,input().split()))
ans=[[0 for e in range(2*N+3)] for f in range(N+1)]
ans[0][N+1]=1
for n in range(1,N+1):
 for i in range(N+1-n,N+2+n):
  ans[n][i]=ans[n-1][i-1]*P[n-1]+ans[n-1][i+1]*(1-P[n-1])
t=0
for i in range(N+1,2*N+3):
 t+=ans[N][i]
print(t)

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input())
p = list(map(float, input().split()))
dp = [[0]*(N+1) for _ in range(N+1)]
dp[0][0] = 1

for i in range(N):
    for j in range(N+1):
        if j+1<=N:
            dp[i+1][j+1] += p[i]*dp[i][j]
            
        dp[i+1][j] += (1-p[i])*dp[i][j]

print(sum(dp[N][N//2+1:]))

Solution (Python):
from sys import stdin, stdout
from collections import deque, defaultdict
import math as m

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	n = int(rl())
	P = [0]
	P.extend(list(rlf()))

	dp = [[0 for j in range(n+1)] for i in range(n+1)]
	dp[0][0] = 1
	for c in range(1, n + 1):
		dp[0][c] = dp[0][c-1]*(1 - P[c])

	for r in range(1, n + 1): 
		for c in range(r, n + 1): 
			dp[r][c] = P[c]*dp[r-1][c-1] + (1- P[c])*dp[r][c-1]

	ans = sum(dp[i][n] for i in range(m.ceil(n/2), n + 1))
	print(ans)
	
	stdout.close()

if __name__ == "__main__":
	main()

Solution (Python):
n = int(input())
p = list(map(float, input().split()))
dp = []
for i in range(n+1):
    dp.append([0]*(n+1))
dp[0][0]=1
for i in range(1,n+1):
    dp[i][0]=(1-p[i-1])*dp[i-1][0]
for i in range(1,n+1):
    for j in range(1,n+1):
        dp[i][j]=p[i-1]*dp[i-1][j-1]+(1-p[i-1])*dp[i-1][j]
ans=0
for i in range(n//2+1,n+1):
    ans+=dp[n][i]
print(ans)

Solution (Python):
N = int(input())
p = list(map(float, input().split()))

dp = [[0 for _ in range(N+1)] for _ in range(N+1)]



for i in range(N):
    for j in range(i+1):
        
        

        if i == 0:
            dp[i+1][j] += 1-p[i]
            dp[i+1][j+1] += p[i]
        else:
            dp[i+1][j] += (1-p[i])*dp[i][j]
            dp[i+1][j+1] += p[i]*dp[i][j]
        

ans = 0
for i, v in enumerate(dp[-1]):
    if i > N//2:
        ans += v

print(ans)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
p=list(map(float,input().split()))

dp=[defaultdict(float) for i in range(n)]

dp[0][1]=p[0]
dp[0][-1]=1-p[0]

for i in range(n-1):
    for j in range(-i-1,i+2):
        
        if j==0:
            dp[i+1][1]+=dp[i][0]*p[i+1]
            dp[i+1][-1]+=dp[i][0]*(1-p[i+1])
        else:
            dp[i+1][j+1]+=dp[i][j]*p[i+1]
            dp[i+1][j-1]+=dp[i][j]*(1-p[i+1])
ans=0.0
for i in range(n):
    ans+=dp[-1][i+1]



print(ans)

Solution (Python):
n=int(input())
import math
p=list(map(float,input().split()))
for i in range(n):
    p[i]=p[i]*100
dp=[[0]*(n) for i in range(n+1)]
dp[0][0]=(100-p[0])/100
for i in range(1,n):
    dp[0][i]=dp[0][i-1]*(100-p[i])/100

for i in range(1,n+1):
    for j in range(i-1,n):
        if j==0:
            temp1=1 
            temp2=0 
        else:
            temp1=dp[i-1][j-1]
            temp2=dp[i][j-1]
        dp[i][j]=temp1*p[j]/100+temp2*(100-p[j])/100
        dp[i][j]=dp[i][j]
ans=0

for i in range(n//2+1,n+1):
    ans+=dp[i][n-1]
print(ans)

Solution (Python):
n=int(input())
h=list(map(float,input().split()))

dp=[[1.0]*(n+1) for i in range(n+1)]
dp[0][0]=1.0

for i in range(1,n+1):
    dp[0][i]=0.0

for i in range(1,n+1):
    dp[i][0]=dp[i-1][0]*(1.0-h[i-1])

for i in range(1,n+1):
    for j in range(1,n+1):
        dp[i][j]= h[i-1]*dp[i-1][j-1]+ (1-h[i-1])*dp[i-1][j]

ans=0
for i in range(n//2+1,n+1):
    ans+=dp[n][i]
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
from collections import defaultdict as dd    
n=int(input())
l=list(map(float,input().split()))
dp=[[0]*(n+1) for i in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
    for j in range(n+1):
        if(j==0):
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])
        else:
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])+dp[i-1][j-1]*l[i-1]
ans=0
for i in range(n//2+1,n+1):
    ans+=dp[n][i]
print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    P=list(map(float,input().split()))
    dp=[[0]*(n+1) for _ in range(n)]
    dp[0][0]=1-P[0]
    dp[0][1]=P[0]
    for i in range(1,n):
        for j in range(i+2):
            if j==0:
                dp[i][j]=dp[i-1][j]*(1-P[i])
            else:
                dp[i][j]=dp[i-1][j-1]*P[i]+dp[i-1][j]*(1-P[i])
    print(sum(dp[-1][n//2+1:]))
if __name__=='__main__':
    main()

Solution (Python):

N=int(input())
P=[0]+[float(x) for x in input().split()]

dp=[0 for i in range(N+1)]
for i in range(N+1):
    dp[i]=[0 for j in range(i+1)]

dp[1][0]+=1-P[1]
dp[1][1]+=P[1]
for i in range(1,N):
    for j in range(i+1):
        p=P[i+1]
        dp[i+1][j+1]+=dp[i][j]*p
        dp[i+1][j]+=dp[i][j]*(1-p)
ans=0        
for i in range(int((N-1)/2)+1,N+1):
    ans+=dp[N][i]
    
print(ans)

Solution (Python):
import numpy as np

if __name__=='__main__':
    N = int(input())
    p = np.array(list(map(float,input().split())))
    
    dp = np.zeros([N+1,N+1],dtype=float)
    dp[0][0] = 1.0
    
    for i,p in enumerate(p):
        dp[i+1][:] = dp[i][:]*(1-p)
        dp[i+1][1:] += dp[i][:-1]*p
    
    
    ans = N//2 + 1
    print(dp[N][ans:].sum())

Solution (Python):
n,l=int(input()),list(map(float,input().split()))
dp=[[0.0]*(n+1) for _ in range(n+1)]
dp[0][0]=1.0
for i in range(1,n+1):
    for j in range(i+1):
        if j==0:
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])
        else:
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])+dp[i-1][j-1]*l[i-1]
print(sum(dp[n][((n+1)//2):]))

Solution (Python):
import sys
sys.setrecursionlimit(1000000) 

def main():
    input = sys.stdin.readline  
    N = int(input())
    probability = list(map(float, input().rstrip().split()))

    
    dp = [[0] * (N+1) for _ in range(N+1)]
    dp[0][0] = 1

    for i, p in enumerate(probability, 1):
        for j in range(i+1):
            if j != 0:
                
                dp[i][j] = dp[i-1][j] * (1-p) + dp[i-1][j-1] * p
            else:
                
                dp[i][j] = dp[i-1][j] * (1-p)
    print(sum(dp[N][(N+1)//2:]))

if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin, stdout


def solve():
    n = int(input())
    A = [float(i) for i in stdin.readline().split()]
    dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(1, n+1):
        for j in range(0, i+1):
            if j == 0: dp[i][j] = (1 - A[i-1]) * dp[i-1][j]
            else: dp[i][j] = (A[i-1] * dp[i-1][j-1]) + ((1 - A[i-1]) * dp[i-1][j])
    ans = 0
    for i in range((n+1)//2, n+1):
        ans += dp[-1][i]
    return ans

print(solve())