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):
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]
    P = []
    input_raw = read_func().strip().split()
    for i in range(N):
        P.append(float(input_raw[i]))

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

            

    count = 0L
    for j in range(N/2 + N%2, N + 1):
        count += dp[N][j]
    print count
if __name__ == '__main__':
    main()

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


if __name__ == "__main__":
    main()

Solution (Python):
n = input()
p = map(float, raw_input().strip().split())

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

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

ans = 0
for k in xrange(n + 1):
    if 2 * k > n: ans += dp[i][k]

print "{0:.10f}".format(ans)

Solution (Python):
n=int(input())
ans=[None]*(n+1)
for i in range(n+1):
  ans[i]=[0]*(n+1)
l=list(map(float,input().split()))
for i in range(n+1):
  ans[0][i]=0
for i in range(1,n+1):
  for j in range(0,n+1):
    if(i==1):
      if(j==0):
        ans[i][j]=1-l[0]
        continue
      elif(j==1):
        ans[i][j]=l[0]
        continue
      else:
        break
    if(j==0):
      ans[i][0]=ans[i-1][0]*(1-l[i-1])
      continue
    ans[i][j]=ans[i-1][j-1]*l[i-1] + ans[i-1][j]*(1-l[i-1])
a=0
import math
for i in range(math.ceil(n/2),n+1):
  a+=ans[n][i]
print(a)

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

Solution (Python):

n = input()
p = map(float, raw_input().split())

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

Solution (Python):
n=int(input())
p=list( float(s) for s in input().split() )
res=[1-p[0], p[0]]+[0]*(n//2 - 1)
for i in range(1,n):
    p1=p[i]
    p0=1-p[i]
    res[len(res)-1]=p0*res[len(res)-1]
    for j in range(len(res)-2, -1, -1):
        res[j+1]+=(res[j]*p1)
        res[j]=(res[j]*p0)        
print( (1-sum(res[:1+n//2])) )

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

Solution (Python):
import numpy as np
n=int(input())
P=np.array(list(map(float,input().split())))
DP=np.zeros(n+1)
DP[0]=1.0

for i in range(n):
  DP = np.roll(DP * P[i], 1) + DP * (1-P[i])
print(sum(DP[n//2+1:]))

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

DP = [[0 for n 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):
    use = P[i]
    DP[i][0] = DP[i-1][0] * (1-use)
    for j in range(1, i+2):
        DP[i][j] = DP[i-1][j] * (1-use) + DP[i-1][j-1] * use

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

Solution (Python):
N = int(input())
P = list(map(float, input().split()))
dp = [[0 for _ in range(N+1)] for _ in range(1, N+1, 2)]

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

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

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

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

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

Solution (Python):

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

import numpy as np
dp = np.full(N+1, 0, dtype=np.float64)
dp[0] = 1
n_p = np.array(p)

for i in range(N):
    tmp      = np.zeros_like(dp)
    tmp[1:]  = dp[:-1] * n_p[i]
    tmp[:-1]+= dp[:-1] * (1-n_p[i])
    dp = tmp

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

Solution (Python):


"""
参考：https://qiita.com/drken/items/03c7db44ccd27820ea0d
・確率DP
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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

print('{:.10f}'.format(sum(dp[N][ceil(N, 2):])))

Solution (Python):
import sys

N=input()
P=map(float,  sys.stdin.readline().split() )

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


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

n=N/2+1

ans=0
for i in range(n, N+1):
	ans+=dp[-1][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):
        if j + 1 <= 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()))
    
dp = [[0]*(n+1) for _ in range(n+1)]
dp[0][0] = 1

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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LF()
    r = [1]
    for i in range(n):
        t = [0] * (i+2)
        ai = a[i]
        a1 = 1 - a[i]
        for j in range(i+1):
            t[j] += r[j] * a1
            t[j+1] += r[j] * ai
        r = t

    return "{:0.10f}".format(sum(r[n//2+1:]))


print(main())

Solution (Python):
import numpy as np
n = int(input())
p = [float(i) for i in input().split()]
dp  = np.array([0.0] * (n + 1))
dp[0] = 1
for i in range(n):
 ura = dp*(1-p[i])
 ura[1:] += dp[:-1] * p[i]
 dp = ura

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

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

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

pre = []
post = [1]

for i in range(N):
    pre = post
    post = [0] * (i+2)
    for j in range(i+2):
        if j > 0:
            post[j] += pre[j-1] * P[i]
        if j <= i:
            post[j] += pre[j] * (1-P[i])

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

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

Solution (Python):
from __future__ import division
import sys
raw_input = sys.stdin.readline
N = int(raw_input())
ans = [0 for x in range(N+1)]
ans[0] = 1
arr = map(float,raw_input().split())
for i in range(N):
    a = arr[i]
    for j in range(i+1,0,-1):
        ans[j] += ans[j-1]*a
        ans[j-1] *= (1-a)
res = 0
for i in range(int(N/2)+1,N+1):
    res += ans[i]
print res

Solution (Python):
import sys
sys.setrecursionlimit(10**8)

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

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

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

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

print("{:.10f}".format(sum(dp[N][N // 2 + 1:])))

Solution (Python):
import numpy as np

n = int(input())
ppp = list(map(float, input().split()))
dp = np.array([0.0] * (n + 1), dtype=np.float64)
dp[0] = 1
for p in ppp:
    ndp = dp * (1 - p)
    ndp[1:] += dp[:-1] * p
    dp = ndp
print(sum(dp[n // 2 + 1:]))

Solution (Python):
N=int(input())
*p,=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]=dp[i-1][j]*(1-p[i-1])
        if j:dp[i][j]+=dp[i-1][j-1]*p[i-1]

print(sum(dp[N][i] for i in range(N+1) if 2*i>=N))

Solution (Python):
N=int(input())
*p,=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(N+1):
        if j:
            dp[i][j]=dp[i-1][j]*(1-p[i-1])+dp[i-1][j-1]*p[i-1]
        else:
            dp[i][j]=dp[i-1][j]*(1-p[i-1])

t=N//2+1 if N%2 else N//2
ans=0
for i in range(t,N+1):
    ans+=dp[N][i]

print(ans)

Solution (Python):
import numpy as np

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

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

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

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

Solution (Python):
def i_coins(N, P):
    """
    N枚の番号が振られたコインがある。i番目のコインを投げたときに
    表が出る確率はp_i, 裏が出る確率は1-p_iである。
    N枚のコインをすべて投げるとき、表の枚数が裏の枚数を上回る確率を求めよ。
    """
    
    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] * int(j >= 1)
                        + dp[i - 1][j] * (1.0 - P[i - 1]))

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

N = int(input())
P = [float(i) for i in input().split()]
print(i_coins(N, P))

Solution (Python):
N=int(raw_input())
P=[float(x) for x in raw_input().split()]
A=[[0 for i in range(N+1)] for j in range(N+1)]
A[1][0]=1-P[0]
A[1][1]=P[0]
for j in range(2,N+1):
    A[j][0]=A[j-1][0]*(1-P[j-1])
    for k in range(1,j+1):
        A[j][k]=A[j-1][k]*(1-P[j-1]) + A[j-1][k-1]*(P[j-1])
print(sum(A[N][N/2+1:]))

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

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

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

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

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


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

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


N = int(fin())
p_list = [float(elem) for elem in fin().split()]


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


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

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

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

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

dp = [0] * (N+1)
dp[0] = 1
for p in ps:
    pp = 1 - p
    for j in reversed(range(N+1)):
        dp[j] = dp[j]*pp + dp[j-1]*p

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

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


for i in range(1, N):
    for j in range(1, N+1):
        dp[i+1][j] = dp[i][j] * (1 - p[i]) + 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):
N=int(input())
p=[float(i) for i in input().split()]
dp=[[0 for j in range(i+2)] for i 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])
        elif j==i+1:
            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]
ans=0
for j in range(N+1):
    if j>N-j:
        ans+=dp[N-1][j]
print(ans)

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
p = list(lf())

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

Solution (Python):
n = int(raw_input())
p = map(float, raw_input().split())
dp = [[0.00 for i in xrange(3001)] for _ in xrange(3001)]

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

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

res = 0.0
for i in xrange(n + 1):
    red = n - i
    if i > red:
        res += dp[n-1][i]
print res

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

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

for i,p in enumerate(P):
    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):
N=int(input())
P=list(map(float,input().split()))

NOW=[1]

for i in range(N):
    NEXT=[0]*(i+2)

    for j in range(i+1):
        NEXT[j]+=NOW[j]*(1-P[i])
        NEXT[j+1]+=NOW[j]*P[i]

    NOW=NEXT
    

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

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

dp = [[0]*(N+1) for i in range(N+1)]
for i in range(N+1):
    if N <= 2*i:
        dp[N][i] = 1.
for c in range(N-1, -1, -1):
    p = P[c]
    for k in range(N-1, -1, -1):
        dp[c][k] = r = p * dp[c+1][k+1] + (1.-p) * dp[c+1][k]
print("%.10f" % dp[0][0])