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):
n = int(input())
p = list(map(float, input().split()))

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

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

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

print(ans)

Solution (Python):
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N = gete(int)
    
    p = tuple(geta(float))

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

    for i, pi in enumerate(p, 1):
        qi = 1 - pi
        dpi = dp[i]
        dpi1 = dp[i - 1]

        dpi[0] = dpi1[0] * qi

        for j in range(1, i + 1):
            dpi[j] = dpi1[j - 1] * pi + dpi1[j] * qi

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


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    n = int(input())
    p = tuple(map(float, input().split()))
    
    
    
    
    
    dp = [[0.0] * (n + 1) for _ in range(n + 1)]
    
    dp[0][0] = 1.0 
    for i0 in range(1, n + 1):
        dp[i0][0] = dp[i0-1][0] * (1 - p[i0-1])

    for i1 in range(1, n + 1):
        pe = p[i1 - 1]
        pre = 1 - pe
        for i2 in range(1, i1 + 1):
            dp[i1][i2] = dp[i1-1][i2] * pre + dp[i1-1][i2-1] * pe

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

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict as dd
mod = pow(10, 9) + 7
mod2 = 998244353
inf = int(1e20)
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(" ".join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


n = int(data())
arr = list(map(float, data().strip().split()))
dp = dd(lambda: dd(float))
dp[0][0] = 1
for i in range(1, n+1):
    dp[i][0] = dp[i-1][0] * (1.0 - arr[i-1])
answer = 0.0
for i in range(1, n+1):
    for j in range(1, n+1):
        dp[i][j] = arr[i-1] * dp[i-1][j-1] + (1.0 - arr[i-1]) * dp[i-1][j]
        if j >= n//2+1 and i == n:
            answer += dp[i][j]
out(answer)

Solution (Python):

import sys


def solve(N: int, p: "List[float]"):
    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 == 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]

    res = 0
    for j in range(N//2+1, N+1):
        res += dp[N][j]
    print(res)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    p = [float(next(tokens)) for _ in range(N)]  
    solve(N, p)


if __name__ == '__main__':
    main()

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

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

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

x=int(n/2)
x=n-x
ans=0

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


print(ans)

Solution (Python):
n=int(input())
h=list(map(float,input().split()))
t=[]
for i in range(n+1):
    temp=[1]*(n+1)
    t.append(temp)
for i in range(1,n+1):
    for j in range(i+1):
        if j==0:
            t[i][j]=t[i-1][0]*(1-h[i-1])
        elif i==j:
            t[i][j]=t[i-1][j-1]*(h[i-1])
        else:
            t[i][j]=(t[i-1][j-1]*(h[i-1]))+(t[i-1][j]*(1-h[i-1]))
a=0
for i in range(n//2+1,n+1):
    a+=t[n][i]
print(a)

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.0

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

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

Solution (Python):
import sys
sys.setrecursionlimit(2000)
input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(float, input().split())
LIN=lambda : list(IN())
mod=1000000007



def main():
	n = int(input())
	
	
	al = LIN()
	
	p = [[0]*(n+1) for _ in range(n+1)]
	p[0][0]=1
	for i in range(1, n+1):
		for j in range(n+1):
			omote = al[i-1]
			ura = 1 - omote
			p[i][j] += p[i-1][j]*ura
			if j > 0:
				p[i][j] += p[i-1][j-1]*omote
	k = p[-1][(n+1)//2:]
	
	r = sum(k)
	print(r)


memo_s=[]
al=[1,1]
n=1
def cc(state, maisuu):
	nokori = n-state
	if maisuu==0:
		return 1
	if nokori < maisuu:
		return 0
	global memo_s
	k = memo_s[state][maisuu]
	if k >= 0:
		return k
	
	omote = al[state]
	ura = 1-omote
	r = cc(state+1, maisuu-1)*omote
	r += cc(state+1, maisuu)*ura
	
	memo_s[state][maisuu]=r
	return r
	
def main2():
	global n
	n = int(input())
	global memo_s
	memo_s = [[-1]*(n+1) for _ in range(n+1)]
	
	v = LIN()
	global al
	al=v[:]
	
	r = cc(0, (n+1)//2)
	print(r)
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

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

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(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 // 2 + 1, n + 1):
    ans += dp[n][i]
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    dp = [0] * (n + 1)
    dp[0] = 1
    for p in map(float, input().split()):
        ndp = [0] * (n + 1)
        for i in range(n):
            ndp[i + 1] += dp[i] * p
        for i in range(n):
            ndp[i] += dp[i] * (1 - p)
        dp = ndp

    res = 0
    for i in range(n + 1):
        if 2 * i > n:
            res += dp[i]
    print(res)
resolve()

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

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):
        if i < j:
            DP[i][j] = 0
        else:
            DP[i][j] = P[i-1] * DP[i-1][j-1] + (1 - P[i-1]) * DP[i-1][j]
print(sum(DP[N][N//2 + 1:]))

Solution (Python):
N=int(input())
p=list(map(float,input().split()))
import numpy as np
d=np.zeros(N+2)
d[1]=1
for i in range(N):
    d[1:i+3]=(d[:i+2]*p[i]+d[1:i+3]*(1-p[i]))
print(sum(d[N//2+2:]))

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq
LI = lambda : [float(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N = NI()
p = LI()
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,i+1):
        dp[i][j] = dp[i-1][j-1] * p[i-1] + dp[i-1][j] * (1-p[i-1])

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

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq
LI = lambda : [float(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N = NI()
p = LI()
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,i+1):
        if j > 0: dp[i][j] = dp[i-1][j-1] * p[i-1]
        dp[i][j] += dp[i-1][j] * (1-p[i-1])

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

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq
LI = lambda : [float(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N = NI()
p = [0.0] + LI()
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,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])

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

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq
LI = lambda : [float(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N = NI()
p = [0.0] + LI()
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] = dp[i-1][j-1] * p[i]
        dp[i][j] += dp[i-1][j] * (1-p[i])

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

Solution (Python):
from collections import defaultdict,deque
import sys, bisect, math, itertools
from functools import lru_cache

sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

n = inp()
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):
        dp[i + 1][j + 1] += dp[i][j] * p[i]  
        dp[i + 1][j] += dp[i][j] * (1.0 - p[i])  

print(sum([dp[n][i] for i in range(math.ceil(n / 2), n + 1)]))

Solution (Python):

"""
Created on Tue May  5 00:32:28 2020

@author: Kanaru Sato
"""

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

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

for i in range(n,0,-1):
    index = i-1
    for j in range(n-i+2):
        if index == n-1 and j == 0:
            dp[index][j] = 1-p[n-1]
        elif index == n-1 and j == 1:
            dp[index][j] = p[n-1]
        elif j == 0:
            dp[index][j] = dp[index+1][j]*(1-p[index])
        elif 1 <= j and j <= n-i:
            dp[index][j] = dp[index+1][j]*(1-p[index]) + dp[index+1][j-1]*(p[index])
        else:
            dp[index][j] = dp[index+1][j-1]*(p[index])

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

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.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]) 

res = 0
for j in range(n + 1):
	if n < 2 * j: 
		res += dp[n][j]

print(res)

Solution (Python):
n=int(input())
p=tuple(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):
    dp[i][j]=dp[i-1][j]*(1-p[i-1])
    if j>0:
      dp[i][j]+=dp[i-1][j-1]*p[i-1]
print(sum(dp[n][n//2+1:]))

Solution (Python):
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n = ni()
p = nfa()

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])

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

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

Solution (Python):

N=int(input())
coin=list(map(float,input().split()))
p=10**9+7
ma=[]
dp=[[0]*(N+3) for i in range(N+3)]
dp[1][1]=coin[0]
dp[1][0]=1-coin[0]
for i in range(1,N):
     for j in range(0,N):
         if j==0:
             dp[i+1][0]=dp[i][0]*(1-coin[i])
         dp[i+1][j+1]=dp[i][j+1]*(1-coin[i])+dp[i][j]*coin[i]

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

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

Solution (Python):
from numpy import zeros

N = int(input())
P = map(float, input().split())

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

for p in P:
    T = dp
    dp = T * (1 - p)
    dp[1:] += T[:-1] * p

print(dp[-(-N // 2):].sum())

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

dp = [1] + [0] * N
for p in P:
    dp = [p * a + (1 - p) * b for a, b in zip([0] + dp, dp)]

print(sum(dp[-(-N // 2):]))

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

dp = [1] + [0] * N
for i, p in enumerate(P, 1):
    dp = [p * a + (1 - p) * b for a, b in zip([0] + dp, dp)]

print(sum(dp[-(-N // 2):]))

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

dp = [0.0] * (N + 1)
dp[0] = 1.0

for i, p in enumerate(P, 1):
    dp = [p * a + (1 - p) * b for a, b in zip([0] + dp, dp)]

print(sum(dp[-(-N // 2):]))

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

dp = [0.0] * (N + 1)
dp[0] = 1.0

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

print(sum(dp[-(-N // 2):]))

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

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

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

print(sum(dp[N][-(-N // 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):
    dp[i][0]=dp[i-1][0]*(1-p[i-1])

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):]))

Solution (Python):
import sys
import numpy as np

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
P = np.array([np.float64(p) for p in readline().split()], dtype=np.float64)


def solve():
    dp = np.zeros(N + 1, dtype=np.float64)
    dp[0] = 1.0 - P[0]
    dp[1] = P[0]
    for i in range(1, N):
        p = P[i]
        q = np.zeros_like(dp)
        q[1:] = dp[:-1]
        dp = dp * (1.0 - p) + q * p
    return dp[N // 2 + 1 :].sum()


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

Solution (Python):
import sys
import copy

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
P = list(map(float, readline().split()))


def solve():
    dp = [0.0] * (N + 1)
    dp[0] = 1.0 - P[0]
    dp[1] = P[0]
    for i in range(1, N):
        ndp = [0.0] * (N + 1)
        p = P[i]
        for j in range(i, -1, -1):
            ndp[j + 1] += dp[j] * p
            ndp[j] += dp[j] * (1 - p)
        dp = ndp
    return sum(dp[N // 2 + 1 :])


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

Solution (Python):
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(n + 1):
        dp[i][j] = dp[i - 1][j] * (1 - p[i - 1]) + dp[i - 1][j - 1] * p[i - 1]
ans = sum(dp[n][i] for i in range(n // 2 + 1, n + 1))
print(ans)

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

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

Solution (Python):
def main():
    N = int(input())
    p = tuple(map(float, input().split()))

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

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

            dp[j] = dp[j]*(1-p[i]) + dp[j-1]*p[i]
            
            

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


main()

Solution (Python):
from math import ceil
def main():
    N = int(input())
    P = list(map(float,input().split()))
    f = [[0]*(N + 1) for _ in range(N + 1)]
    f[0][0] = 1 - P[0]
    f[0][1] = P[0]
    for i in range(1,N):
        p = P[i]
        f[i][0] = f[i - 1][0]*(1 - p)
        for j in range(max(1,ceil((N + 1)/2) - N + i - 3),i + 2):
            f[i][j] += p*f[i - 1][j - 1] + (1 - p)*f[i - 1][j]
    print(sum(f[N - 1][N //2 + 1:]))
    return

if __name__ == "__main__":
    main()

Solution (Python):
from math import ceil
def main():
    N = int(input())
    P = list(map(float,input().split()))
    f = [[0]*(N + 1) for _ in range(N + 1)]
    f[0][0] = 1 - P[0]
    f[0][1] = P[0]
    for i in range(1,N):
        p = P[i]
        f[i][0] = f[i - 1][0]*(1 - p)
        for j in range(max(1,ceil((N + 1)/2) - N + i - 3),i + 2):
            f[i][j] += p*f[i - 1][j - 1] + (1 - p)*f[i - 1][j]
    print(sum(f[N - 1][N //2 + 1:]))
    return

if __name__ == "__main__":
    main()

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

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(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+1)//2:]))

Solution (Python):
import numpy as np

N = int(input())
P = tuple(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][1:] += dp[i][:-1] * P[i]
    dp[i + 1][:-1] += dp[i][:-1] * (1 - P[i])
print(sum(dp[N][(N + 1) // 2:]))

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

dp = [[0 for _ in range(N + 1)] for __ 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])
print(sum(dp[N][(N + 1) // 2:]))

Solution (Python):
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 j in range(N+1):
        if j==0:
            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//2+1:]))

Solution (Python):
n = int(input())
*P, = map(float, input().split())
DP = [[0.0 for j in range(n+1)] for i in range(n+1)]
DP[0][0] = 1.0
for i in range(1, n+1):
    DP[i][0] = DP[i-1][0]*(1-P[i-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+1)//2:]))

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


def solve():
    dp = [[0]*(i+3) for i in range(N+1)]
    dp[0][1] = 1
    for i in range(1,N+1):
        for j in range(1,i+2):
            dp[i][j] = dp[i-1][j-1]*P[i-1]+dp[i-1][j]*(1-P[i-1])
    ans = sum(dp[-1][(N+3)//2:])
    return ans
print(solve())

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


def solve():
    dp = [[0]*(i+2) 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-P[i-1])
    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-1][j]*(1-P[i-1])
    ans = sum(dp[-1][(N+2)//2:])
    return ans
print(solve())

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


def solve():
    dp = [[0]*(N+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(1,N+1):
        dp[i][0] = dp[i-1][0]*(1-P[i-1])
    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-1][j]*(1-P[i-1])
    ans = sum(dp[-1][(N+2)//2:])
    return ans
print(solve())

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(N):
    for j in range(i + 1):
        dp[i + 1][j] += dp[i][j] * (1 - P[i])
        dp[i + 1][j + 1] += dp[i][j] * P[i]

ans = 0

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

print(ans)

Solution (Python):






"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy


def prob(i, values):
    result = 1
    idx = 0
    for idx, v in enumerate(values):
        i, rest = divmod(i, 2)
        if rest == 1:
            result *= v
        else:
            result *= 1 - v
        idx += 1
    return result


def solve(values, nb):
    LOG.debug((values))
    dp = [[0] * (nb + 1) for _ in range(nb // 2 + 1)]
    dp[0][0] = 1
    for j in range(1, nb + 1):
        dp[0][j] = dp[0][j - 1] * (1 - values[j - 1])
    total = dp[0][-1]
    for i in range(1, nb // 2 + 1):
        for j in range(i, nb + 1):
            dp[i][j] = (
                dp[i - 1][j - 1] * values[j - 1] + (1 - values[j - 1]) * dp[i][j - 1]
            )
        total += dp[i][-1]
    
    return 1 - total


def do_job():
    "Do the work"
    LOG.debug("Start working")
    
    N = int(input())
    values = list(map(float, input().split()))
    
    
    
    result = solve(values, N)
    
    print("{:.10g}".format(result))


def configure_log():
    "Configure the log output"
    log_formatter = logging.Formatter("L%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None

if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            
            
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Solution (Python):
def main():
    from bisect import bisect_left as bl, bisect_right as br, insort
    import sys
    import heapq
    
    from collections import defaultdict as dd, deque
    def data(): return input()
    def mdata(): return map(float, data().split())
    out = sys.stdout.write
    
    INF = int(1e9)
    mod = int(1e9) + 7

    n = int(data())
    P = list(mdata())
    dp = [0.0] * (n // 2 + 2)
    dp[1] = float(1)
    for i in range(n):
        p=P[i]
        for j in range(len(dp) - 1, 0, -1):
            dp[j] = dp[j - 1] * (1 - p) + dp[j] * (p)
    print(sum(dp))

if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq

from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline()
def mdata(): return map(float, data().split())
out = sys.stdout.write

INF = int(1e9)
mod = int(1e9) + 7

n = int(data())
P = list(mdata())
dp = [0.0] * (n // 2 + 2)
dp[1] = float(1)
for i in range(n):
    p=P[i]
    for j in range(len(dp) - 1, 0, -1):
        dp[j] = dp[j - 1] * (1 - p) + dp[j] * (p)
print(sum(dp))

Solution (Python):
def main():
    from bisect import bisect_left as bl, bisect_right as br, insort
    import sys
    import heapq
    
    from collections import defaultdict as dd, deque
    def data(): return sys.stdin.readline()
    def mdata(): return map(float, data().split())
    out = sys.stdout.write
    
    INF = int(1e9)
    mod = int(1e9) + 7

    n = int(data())
    P = list(mdata())
    dp = [0.0] * (n // 2 + 2)
    dp[1] = float(1)
    for i in range(n):
        p=P[i]
        for j in range(len(dp) - 1, 0, -1):
            dp[j] = dp[j - 1] * (1 - p) + dp[j] * (p)
    print(sum(dp))

if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq

from collections import defaultdict as dd, deque
def data(): return input()
def mdata(): return map(float, data().split())
out = sys.stdout.write

INF = int(1e9)
mod = int(1e9) + 7

n = int(data())
P = list(mdata())
dp = [0.0] * (n // 2 + 2)
dp[1] = float(1)
for i in range(n):
    p=P[i]
    for j in range(len(dp) - 1, 0, -1):
        dp[j] = dp[j - 1] * (1 - p) + dp[j] * (p)
print(sum(dp))

Solution (Python):
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq

from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(float, data().split())
out=sys.stdout.write

INF=int(1e9)
mod=int(1e9)+7


n=int(data())
P=list(mdata())
dp=[0]*(n//2+2)
dp[1]=1
for i in range(n):
    dp1=dp[:]
    for j in range(1,len(dp)):
        k=dp[j-1]*(1-P[i])+dp[j]*(P[i])
        dp1[j]=k
    dp=dp1[:]
print(sum(dp))

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read():
    N = int(input().strip())
    P = list(map(float, input().strip().split()))
    return N, P


def solve(N, P):
    
    
    
    dp = [[0 for j in range(N+1)] for i in range(2)]
    dp[0][0] = 1
    for j in range(1, N+1):
        dp[0][j] = dp[0][j-1] * (1.0 - P[j-1])
    ans = dp[0][-1]
    for i in range(1, N//2+1):
        b = i % 2
        dp[b][i-1] = 0.0
        for j in range(i, N+1):
            dp[b][j] = dp[(b-1)%2][j-1] * P[j-1] + dp[b][j-1] * (1.0 - P[j-1])
        ans += dp[b][-1]
    return "{:.10f}".format(1.0 - ans)


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Solution (Python):
n = int(input())
p = [0] + list(map(float, input().split()))
q = [1 - p[i] for i in range(n + 1)]
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] = dp[i - 1][j] * q[i]
        if not j == 0:
            dp[i][j] += dp[i - 1][j - 1] * p[i]
ans = 0
for i in range((n + 1) // 2):
    ans += dp[n][n - i]
print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
p = list(map(float, readline().split()))
dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1
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 - p[i])
print(sum(dp[-1][n // 2 + 1:]))

Solution (Python):
def solve():
    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):
        for j in range(0,i+1):
            dp[i+1][j+1] += dp[i][j] * p[i]
            dp[i+1][j] += dp[i][j] * (1.0 -p[i])
    

    ans = 0
    for i in range(N+1):
        if i > (N-i):
            ans += dp[-1][i]
    
    print(ans)
            
if __name__ == '__main__':
    solve()

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
for i in range(n):
    for j in range(n):
        if dp[i][j]==0:
            continue
        dp[i+1][j] += dp[i][j] * (1-p[i])
        dp[i+1][j+1] += dp[i][j] * p[i]
print(sum(dp[-1][(n+1)//2:]))