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 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] = (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.0      
for i in range(n//2+1,n+1):
  res += dp[n][i]
  
  
print(res)

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

Solution (Python):




N = int(input())
P = list(map(float, input().split()))
overhalf_N = (N+1)//2
underhalf_N = overhalf_N - 1

dp = [0]*(N+1) 

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

for i in range(overhalf_N,N):
  pc = 1 - P[i]
  for j in range(underhalf_N, 0, -1):
    dp[j] = dp[j-1] * P[i] + dp[j] * pc
  dp[0] = dp[0] * pc

print(1-sum(dp[:overhalf_N]))

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

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

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

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

for i in range(1,N):
    dp[i][0] = (1-p[i])*dp[i-1][0]
    for j in range(1,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[i][j]: i枚投げた時にj枚表の確率
"""
dp = [[0] * (N+1) for _ in range(N+1)]
dp[1][0] = 1 - P[0]
dp[1][1] = P[0]

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

ans = 0
for i in range(N+1):
    if N//2 < i:
        ans += dp[N][i]
print(ans)

Solution (Python):


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    

    

    N = int(input())
    p = tuple(map(float, input().split()))

    
    dp = [1] + [0]*(N//2)
    for i in range(N):
        for j in range(i+1, -1, -1):
            if j==0:
                dp[j] = dp[j]*p[i]
            elif j<=(N//2):
                dp[j] = dp[j-1]*(1-p[i]) + dp[j] * p[i]
    res = sum(dp)
    print('{:.9f}'.format(res))

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    

    
    N = int(input())
    p = list(map(float, input().split()))
    
    dp = [1] + [0]*(N//2)
    for i in range(N):
        for j in range(i+1, -1, -1):
            if j==0:
                dp[j] = dp[j]*p[i]
            elif j<=(N//2):
                dp[j] = dp[j-1]*(1-p[i]) + dp[j] * p[i]

    res = sum(dp)
    print('{:.9f}'.format(res))

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    

    
    N = int(input())
    p = list(map(float, input().split()))
    
    dp = [1] + [0]*(N//2)
    for i in range(N):
        for j in range(i+1, -1, -1):
            if j==0:
                dp[j] = dp[j]*p[i]
            elif j<=(N//2):
                dp[j] = dp[j-1]*(1-p[i]) + dp[j] * p[i]

    res = sum(dp)
    print('{:.9f}'.format(res))


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
P = list(map(float, input().split()))
import numpy as np
def prob_ret():
  prob = [0.0]*(N+1)
  prob[0] = 1
  prob=np.array(prob)
  for n in range(N):
    p = prob[:N]*P[n]
    prob = prob * (1-P[n])
    prob[1:] = prob[1:] + p
  return sum(prob[N//2+1:])
print(prob_ret())

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














dp = [[0] * 1501 for i in range(3000)]
dp[n][0] = 1
for i in reversed(range(n)):
    for at in reversed(range((n + 1) // 2 + 1)):
        r = dp[i + 1][max(0, at - 1)] * a[i] + dp[i + 1][at] * (1 - a[i])
        dp[i][at] = r

print(dp[0][(n + 1) // 2])

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

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

for i in range(n-1):
    for j in range(n+1):
        if dp[i][j]!=0:
            
            dp[i+1][j+1]+=dp[i][j]*p[i+1]
            
            dp[i+1][j]+=dp[i][j]*(1-p[i+1])
print(sum(dp[-1][mid:]))

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

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

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

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

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

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

print(ans)

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

l = [1]

for i in range(n):
    t1 = [j*(1-p[i]) for j in l]
    t1.append(0)
    t2 = [0]+[j*p[i] for j in l]
    l = [t1[j] + t2[j] for j in range(len(t1))]

l.reverse()
print(sum([l[i] for i in range((n+1)//2)]))

Solution (Python):
N=int(input())
P=list(map(float,input().split()))
C=[[0.00]*(N+1) for i in range(N+1)]
C[0][0]=1.00
for i in range(1,N+1):
    for j in range(0,i+1):
        """
        
        print(P[i-1])
        print(C[i-1][j-1])
        print(C[i-1][j-1]*P[i-1])
        """
        C[i][j]=float(C[i-1][j-1]*P[i-1])+float(C[i-1][j]*(1-P[i-1]))
        
ans=float(0.00)
for i in range((N-1)//2+1):
    ans+=C[N][i]
ans=float(1.00-ans)
print(ans)

Solution (Python):
import numpy as np

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

dp = np.zeros(N + 2)
dp[1] = 1

for p in P:
    q = 1 - p
    dp[1:] = dp[:N + 1] * p + dp[1:] * q


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

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

Solution (Python):

N = int(input())

fac = [1]
for i in range(N):
    i += 1
    fac.append(fac[-1] * i)

def nCr(n,r):
    return fac[n] // (fac[r] * fac(n-r))

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

"""

dpだよな
表と裏がa,N-a枚となる確率は？
無理かなぁ

左から見ていってdp?
表がa枚になる確率は p*(a-1枚の確率) + (1-p)*(a枚の確率)
→いけそう

"""

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

for loop in range(N):

    ndp = [0] * (N+1)

    for i in range(N):

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

    dp = ndp

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

print (ans)

Solution (Python):
import collections
N = int(input())
A = list(map(float,input().split()))
K = N//2  + 1
dp = [[0 for _ in range(N + 1) ] for _ in range(N + 1)]
if N == 0: 
    print(0)
    exit
dp[0][0] = 1
ans = 0
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])
        else:
            dp[i][j] = dp[i-1][j-1]*A[i-1] + dp[i-1][j]*(1-A[i-1])
for i in range(K,len(dp[N])):
        ans+=dp[N][i]
print(ans)

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

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

    for i, p in enumerate(P):
        p2 = 1 - p
        for j in range(i + 1, -1, -1):
            if j >= 0:
                dp[j] = dp[j] * p2 + dp[j - 1] * p
            else:
                dp[j] = dp[j] * p2

    ldp = len(dp)
    s = ldp - len(dp) // 2

    print(sum(dp[s:]))

main()

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

    ans=0
    for j in range(-(-N//2)):
        ans+=dp[N][j]

    print(ans)

    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())
P = list(map(float, input().split()))

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


print(sum(dp[-2][-(-(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(1, N + 1):
  for j in range(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]) 

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

print(ans)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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

Solution (Python):
import sys
import math
from collections import deque
import copy

N = int(input())
p = list(map(float, input().split()))
if N == 1:
    print(p[0])
    sys.exit()
dp = [[0 for _ in range(N + 10)] for _ in range(N + 10)]
dp[2][0] = (1.0 - p[0]) * (1.0 - p[1])
dp[2][2] = p[0] * p[1]
dp[2][1] = 1.0 - dp[2][0] - dp[2][2]
for i in range(2, N):
    for l in range(0, N + 1):
        dp[i + 1][l + 1] += dp[i][l] * p[i]
        dp[i + 1][l] += dp[i][l] * (1.0 - p[i])
ans = 0.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)]
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-p[i])

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


print(ans)

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

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

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

n2 = n//2
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+1][j] + dp[i][j]*(1-p[i])
        dp[i+1][j+1] = dp[i+1][j+1] + dp[i][j]*p[i]

print(sum(dp[-1][n2+1:]))

Solution (Python):
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue


Mod = 1000000007
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res
 
def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)
 
 
 
        
def main(): 
    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(i+1):
            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)//2,n+1):
        ans += dp[n][i]
    print(ans)
 
if __name__ == "__main__":
    main()

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

def main():
    N = int(input())
    p0_list = np.array([float(item) for item in input().split()])
    p1_list = 1 - p0_list

    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] * p1_list[i]
        dp[i+1][1:]  += dp[i][:-1] * p0_list[i]

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

if __name__ == "__main__":
    main()

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

N = int(input())
p0_list = np.array([float(item) for item in input().split()])
p1_list = 1 - p0_list

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] * p1_list[i]
    dp[i+1][1:]  += dp[i][:-1] * p0_list[i]

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

Solution (Python):
N = int(input()) 
tmp = [float(i) for i in input().split()]
dp = [0 for i in range(N+1)] 
dp[0] = 1

for i in range(N):
  k = tmp[i]
  
  
  
  for j in range(i+1, -1, -1):
    dp[j] = dp[j-1] * k + dp[j] * (1-k)
ans = 0
for i in range(N+1):
  tails = N-i
  if tails < i:
    ans += dp[i]
print("%s" % ans)

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

Solution (Python):
def main():
  import numpy as np
  n=int(input())
  p=np.array([float(i) for i in input().split()])
  
  dp=np.zeros([n+1,n+1],dtype=np.float64)
  dp[0][0]=1
  for i in range(n):
    tmp=np.roll(dp[i],1)
    tmp[0]=0
    dp[i+1]+=dp[i]*(1-p[i])+tmp*p[i]
    

  print(sum(dp[n][(n+1)//2:]))
      
if __name__=='__main__':
  main()

Solution (Python):
def main():
  n=int(input())
  p=[float(i) for i in input().split()]
  
  dp=[[0]*(n+1) for i in range(n+1)]
  dp[0][0]=1
  for i in range(n):
    dp[i+1][0]=dp[i][0]*(1-p[i])
    for j in range(i+1):
      dp[i+1][j+1]=dp[i][j]*p[i]+dp[i][j+1]*(1-p[i])
  print(sum(dp[n][(n+1)//2:]))
      
if __name__=='__main__':
  main()

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

n = int(input())
p = [float(x) for x in input().split()]

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

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

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

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

Solution (Python):
def main():
    import sys
    readline = sys.stdin.readline

    n = int(readline())
    *p, = (float(pi) for pi in readline().rstrip().split())

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

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

    ret = sum(dp[n][j] for j in reversed(range(n + 1)) if j * 2 > n)
    print(ret)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
l = 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(i+1):
    dp[i+1][j+1] += dp[i][j] * l[i]
    dp[i+1][j] += dp[i][j] * (1-l[i])
    
ans_ = 0
for i in range(0, n//2+1):
  ans_ += dp[n][i]
print(1-ans_)

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

dp=[[0.0]*(n+1) for i 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])

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

Solution (Python):
import numpy as np

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

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

dp = [0 for j in range(n + 1)]
dp[0] = 1
for i in range(n):
    pi = p[i]
    for j in range(i, -1, -1):
        dp[j + 1] = dp[j + 1] * pi + dp[j] * (1 - pi)
    dp[0] *= pi
print(sum(dp[:n // 2 + 1]))

Solution (Python):
N = int(input())
p_f = [0.0]
p_b = [0.0]
for p in list(map(float,input().split())):
    p_f.append(p)
    p_b.append(1.0-p)


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

def cointoss(n_toss):
    global p_majority
    for i in range(n_toss):
        dp[n_toss][i+1] += dp[n_toss-1][i] * p_f[n_toss]
        dp[n_toss][i  ] += dp[n_toss-1][i] * p_b[n_toss]

for i in range(1,N+1):
    cointoss(i)

p_majority = 0.0
n_majority = N // 2 + 1

for i in range(n_majority,N+1):
    p_majority += dp[N][i]

print(p_majority)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

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

if __name__ == '__main__':
    main()

Solution (Python):
from copy import copy
N = int(input())
P = list(map(float,input().split()))
dp = [0. for i in range(N+1)]
for i in range(N):
    if i == 0:
        dp[0] = 1. - P[i]
        dp[1] = P[i]
    else:
        new_dp = copy(dp)
        for j in range(N+1):
            if j == 0:
                new_dp[j] = dp[j]*(1-P[i])
            else:
                new_dp[j] = dp[j]*(1-P[i]) + dp[j-1]*(P[i])
        dp = copy(new_dp)
print(sum(dp[N//2+1:]))

Solution (Python):
def main():
    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]
    print(sum(dp[N][N//2+1:]))


if __name__ == '__main__':
    main()

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

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


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

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

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

dp = [0 for j in range(n + 1)]
dp[0] = 1
for i in range(n):
    pi = p[i]
    for j in range(i, -1, -1):
        dp[j + 1] = dp[j + 1] * pi + dp[j] * (1 - pi)
    dp[0] *= pi
print(sum(dp[:n // 2 + 1]))

Solution (Python):
n = int(input())
pl = 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(n):
    for j in range(n):
        dp[i+1][j+1] += pl[i] * dp[i][j]
        dp[i+1][j] += (1-pl[i]) * dp[i][j]

def ceil(a, b):
   return a // b + (a % b > 0)
print(sum(dp[-1][ceil(n,2):]))

Solution (Python):
def examA():
    N = I()
    H = LI()
    dp = [inf]*(N)
    dp[0] = 0
    for i in range(N-1):
        dp[i+1] = min(dp[i+1],dp[i]+abs(H[i+1]-H[i]))
        if i<N-2:
            dp[i + 2] = min(dp[i + 2], dp[i]+abs(H[i + 2] - H[i]))
    ans = dp[-1]
    print(ans)
    return

def examB():
    N, K = LI()
    H = LI()
    dp = [inf]*N
    dp[0] = 0
    for i in range(N):
        for k in range(1,K+1):
            if i+k>=N:
                break
            if dp[i+k]>dp[i]+abs(H[i+k]-H[i]):
                dp[i+k] = dp[i]+abs(H[i+k]-H[i])
    ans = dp[-1]
    print(ans)
    return

def examC():
    N = I()
    A = [0]*N; B = [0]*N; C = [0]*N
    for i in range(N):
        A[i],B[i],C[i] = LI()
    dp = [[0]*3 for _ in range(N+1)]
    for i in range(N):
        dp[i+1][0] = max(dp[i][1],dp[i][2]) + A[i]
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + B[i]
        dp[i + 1][2] = max(dp[i][1], dp[i][0]) + C[i]
    ans = max(dp[N])
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    
    S = SI(); N = len(S)
    T = SI(); M = len(T)
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])

    i = N; j = M
    ans = []
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans.append(S[i-1])
            i -= 1
            j -= 1
    print("".join(ans[::-1]))
    return

def examG():
    
    
    def topological_sort(n,outs,ins):
        q = deque(v1 for v1 in range(n) if ins[v1] == 0)
        res = []
        while q:
            v1 = q.popleft()
            res.append(v1)
            for v2 in outs[v1]:
                ins[v2] -= 1
                if ins[v2] == 0:
                    q.append(v2)
        return res
    N, M = LI()
    V = [[]for _ in range(N)]
    start = [0]*N
    for _ in range(M):
        x,y = LI()
        x -= 1; y -= 1
        V[x].append(y)
        start[y] += 1
    Order = topological_sort(N, V, start)

    dp = [0]*N
    for i in Order:
        for v in V[i]:
            dp[v] = max(dp[v],dp[i]+1)
    ans = max(dp)
    print(ans)
    return

def examH():
    H, W = LI()
    A = [SI() for _ in range(H)]
    dp = [[0]*W for _ in range(H)]
    dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            if A[i][j]=="
                continue
            dp[i][j] %=mod
            if i+1<H and dp[i+1][j]!="
                dp[i+1][j] +=dp[i][j]
            if j+1<W and dp[i][j+1]!="
                dp[i][j+1] +=dp[i][j]
    ans = dp[-1][-1]
    print(ans)
    return

def examI():
    N = I()
    P = LFI()
    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])
    ans = 0
    for v in dp[N][(1+N//2):]:
        ans += v
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examI()

"""

"""

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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 

def ii(): return int(sys.stdin.readline().rstrip()) 
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) 
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]

def ss(): return sys.stdin.readline().rstrip() 
def mss(): return sys.stdin.readline().rstrip()
def limss(): return list(mss()) 
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]





n=ii()
arr=list(map(float,sys.stdin.readline().rstrip().split()))

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

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

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

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

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

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

Solution (Python):
import numpy as np
N = int(input())
P = np.array(input().split(), dtype=float)

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

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

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

Solution (Python):
import numpy as np
N = int(input())
P = np.array(input().split(), dtype=float)

dp = np.zeros(N + 1, dtype=float)
dp[0] = 1 - P[0]
dp[1] = P[0]

for i in range(N - 1):
    newDP = dp * (1 - P[i + 1])
    newDP[1:] += dp[:-1] * P[i + 1]
    dp = newDP.copy()

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

Solution (Python):
n = int(input())
pp = 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] * pp[i]
    dp[i+1][j] += dp[i][j] * (1-pp[i])
    
print(sum(dp[-1][(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(N):
    for j in range(N):
        dp[i+1][j]+=dp[i][j]*(1-p[i])
        dp[i+1][j+1]+=dp[i][j]*p[i]
        if j==i:
            break
            
print(1.0-sum(dp[-1][:N//2+1]))