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

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

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

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

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

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

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

print(ans)

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

Solution (Python):
from sys import stdin
def input():
    return stdin.readline().strip()

def main():
    n = int(input())
    probabilities = list(map(float, input().split()))

    
    dp = [0.0] * (n//2 + 3)
    dp[0] = 1.0
    for p in probabilities:
        dp[n//2 + 1] += dp[n//2] * p
        for j in range(n//2 + 1)[::-1]:
            dp[j] = dp[j] * (1 - p) + dp[j-1] * p

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

main()

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

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

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

print(ans)

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

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

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

if __name__=="__main__":
    n,p= getval()
    main(n,p)

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

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

if __name__=="__main__":
    n,p= getval()
    main(n,p)

Solution (Python):
import sys
import math



def input():
    return sys.stdin.readline().rstrip()


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

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

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

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






if __name__ == "__main__":
    main()

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

N = int(input())

def li():
    return [float(x) for x in input().split()]

P = li()

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

dp[0][1], dp[0][0] = P[0], 1 - P[0]

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

total = 0
for j in range(N+1):
    if 2 * j > N:
        total += dp[N-1][j]

print(total)

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

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

Solution (Python):
import numpy as np

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

dp = np.zeros(n+1)
dp[0] = 1

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

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

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

dp = [[0]*3100 for _ in range(3100)]

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

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

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

N = int(readline())
P = list(map(float,readline().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):
    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):
  if i > N // 2:
    ans += dp[-1][i]

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
import decimal
from decimal import Decimal
decimal.getcontext().prec = 10

from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)



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

Solution (Python):
import numpy as np

N = int(input())
P = list(map(float, input().split()))
DP = np.zeros(N+2)
DP[0] = 1
for i, p in enumerate(P, 1):
    DP = DP * (1 - p) + np.roll(DP, 1) * p

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

Solution (Python):
N = int(input())
P = [0] + list(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):
  for j in range(0, N+1):
    if j > 0:
      dp[i][j] = (1-P[i]) * dp[i-1][j] + P[i] * dp[i-1][j-1]
    else:
      dp[i][j] = (1-P[i]) * dp[i-1][j]
ans = 0.0
for j in range(N+1):
  if j * 2 > N:
    ans += dp[N][j]
print(ans)

Solution (Python):
import numpy as np

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

dp = np.zeros((3100, 3100))



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

for i in range(2, N + 1):
    dp[i] = np.roll(dp[i-1], 1) * p[i] + dp[i-1] * (1-p[i])
    
    
    
    

ans = 0

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

print(ans)

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

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

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

Solution (Python):


N=int(input())

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

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

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

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

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

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

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

def main():
    n = int(input())
    plst = 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(i + 1):
            dp[i][j] = dp[i - 1][j - 1] * plst[i - 1] + dp[i - 1][j] * (1 - plst[i - 1])
    ans = 0
    for i in range(n // 2 + 1, n + 1):
        ans += dp[-1][i]
    print(ans)

main()

Solution (Python):
n= int(input())
p =[float(x) for x in 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(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])
an=0
for i in range((n+1)//2,n+1):
    an+=dp[n][i]
print(an)

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


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

Solution (Python):




def recur(parr, curp, curi, heads):
    
    
    if curi >= len(parr):
        if heads >= len(parr)//2 + 1:
            return curp
        else:
            return 0

    return (recur(parr, curp*parr[curi], curi+1, heads+1)
            + recur(parr, curp*(1-parr[curi]), curi+1, heads))

n = int(input())

parr = [float(i) for i in input().split(' ')]



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

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

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

Solution (Python):




def recur(parr, curp, curi, heads):
    
    
    if curi >= len(parr):
        if heads >= len(parr)//2 + 1:
            return curp
        else:
            return 0

    return (recur(parr, curp*parr[curi], curi+1, heads+1)
            + recur(parr, curp*(1-parr[curi]), curi+1, heads))

n = int(input())

parr = [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(1, n+1):
    for j in range(i, -1, -1):
        
        heads = dp[i-1][j-1] if j > 0 else 0
        
        tails = dp[i-1][j]
        dp[i][j] = heads*parr[i-1] + tails*(1-parr[i-1])

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

Solution (Python):
def main():
    N = int(input())
    P = [float(i) for i in input().split()]
    dp = [[0]*(N+1) for _ in range(N+1)]
    dp[1][1] = P[0]
    dp[1][0] = 1 - P[0]
    for i in range(2, N+1):
        p = P[i-1]
        for j in range(i+1):
            p1 = dp[i-1][j-1] * p if j != 0 else 0
            p2 = dp[i-1][j] * (1 - p)
            dp[i][j] = p1 + p2
    ans = 0
    for j in range(0--N//2, N+1):
        ans += dp[N][j]
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
INF=float('inf')

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

Solution (Python):
INF=float('inf')

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

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

for i in range(n+1):
  if i==0:
    dp[0][0]=1
  else:
    dp[i][0]=(1-P[i-1])*dp[i-1][0]

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

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

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

Solution (Python):
def coins(n,prob):
    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-prob[i-1])
            else:
                dp[i][j] = dp[i-1][j]*(1-prob[i-1])+dp[i-1][j-1]*prob[i-1]
    total = 0
    for i in range(n,n//2,-1):
        total+= dp[n][i]
    return total

n = int(input())
prob = list(map(float,input().split()))
print(coins(n,prob))

Solution (Python):
n = int(input())
p = list(map(float,input().split()))
a = [[0 for i in range(n+1)] for j in range(n+1)]
a[0][0] = 1
for i in range(1, n+1):
    for j in range(n+1):
        if j == 0:
            a[i][j] = (1-p[i-1])*a[i-1][j]
        elif(i<j):
            a[i][j] = 0
        else:
            a[i][j] = p[i-1]*(a[i-1][j-1])
            if i-1>=j:
                a[i][j] += (1-p[i-1])*a[i-1][j]
mh = (n+1)//2
ans = 0 
for i in range(mh, n+1):
    ans += a[n][i]
print(ans)

Solution (Python):


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase




from bisect import bisect_right as br
from bisect import bisect







BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)







mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  


def out(var): sys.stdout.write(str(var))  


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  


def testcase(t):
    for p in range(t):
        solve()


from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count



from sys import setrecursionlimit
setrecursionlimit(1000000)



def solve():
    n=int(inp())
    ar=[float(i) for i in inp().strip().split(" ")]
    dp=[[0 for _ in range(n+5)] for i in range(n+5)]
    dp[1][0]=1-ar[0]
    dp[1][1]=ar[0]
    for i in range(2,n+1):
        dp[i][0]=dp[i-1][0]*(1-ar[i-1])
    for i in range(2,n+1):
        for j in range(1,n+1):
            if j>i:
                break
            dp[i][j]=dp[i-1][j]*(1-ar[i-1])+dp[i-1][j-1]*ar[i-1]
    s=0
    for i in range(n//2 +1 ,n+1):
        s+=dp[n][i]

    print(s)






solve()

Solution (Python):


from sys import setrecursionlimit

setrecursionlimit(1000000)






n = int(input())

p = list(map(float, input().split()))
p = [-1] + p

memo = [[-1 for _ in [0] * (n + 1)] for _ in [0] * (n + 1)]
memo[0][0] = 1
for i in range(len(p))[1:]:
    memo[0][i] = 0
    memo[i][0] = memo[i - 1][0] * (1 - p[i])
memo[0][0] = 1


def dp(i, j):
    if memo[i][j] == -1:
        memo[i][j] = dp(i - 1, j) * (1 - p[i]) + dp(i - 1, j - 1) * p[i]
    return memo[i][j]


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

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


print("{}".format(ans))

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

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

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

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

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

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


dp[0][0] = 1 

for i in range(1, nn):
    for j in range(0, nn):
        if j == 0 :
            dp[i][j] = dp[i - 1][j] *(1 - arr[i - 1])
            continue 
        else:
            dp[i][j] = dp[i - 1][j - 1] * arr[i - 1] + dp[i - 1][j] * (1 - arr[i - 1])
lastarr = dp[-1]

half = n // 2 + 1 

ans = 0 
for i in range(half, nn):
    ans += lastarr[i]
print(ans)

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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  
from functools import reduce
from math import gcd

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

'''
dp[i,j]...表がちょうどj回出る確率、コイン[:i]を考慮したとき
dp[i+1,j]+=dp[i,j]*(1-P[i]) 
dp[i+1,j+1]+= dp[i,j]*P[i] 
'''
dp = [[0] * (N + 2) for _ in range(N + 2)]
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]  


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 t in range(1,n+1):
    dp[t][0]=dp[t-1][0]*(1-p[t-1])
    for h in range(1,t+1):
        dp[t][h]=dp[t-1][h-1]*p[t-1]+dp[t-1][h]*(1-p[t-1])
        
        
ans=0
for h in range(t//2+1,n+1):
    ans+=dp[n][h]
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][1]=1-p[0]
dp[1][1]=p[0]

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

Solution (Python):
from collections import deque

def main():
  N = int(input())
  arr = 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 k in range(i + 1):
      dp[i + 1][k + 1] += dp[i][k] * arr[i]
      dp[i + 1][k] += dp[i][k] * (1.0 - arr[i])
  
  ans = 0.0
  for i in range(N // 2 + 1, N + 1):
    ans += dp[N][i]
  
  print(ans)



if __name__ == "__main__":
  main()

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

dp=[[] for _ in range(N)]

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

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

Solution (Python):
N = int(input())
P = list(map(float, input().split()))
P = [0] + P
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])

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

ans = 0
if N % 2 == 0:
    start = N // 2
else:
    start = N // 2 + 1

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

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


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+1, n+1):
        ans += dp[n][i]
            
    print(ans)
    
    
if __name__ == "__main__":
    main()

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


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+1, n+1):
        ans += dp[n][i]
            
    print(ans)
    
    
if __name__ == "__main__":
    main()

Solution (Python):







N = int(input())
p = [0] + 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, i + 1):

        if j > 0:  
            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])

ans = 0

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

print(ans)

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

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

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

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

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

Solution (Python):
N = int(input())
def main():
    head_prob_table = [[0.0] * (N+1) for i in range(N)]
    head_prob = list(map(float, input().split()))

    head_prob_table[0][1] = head_prob[0]
    head_prob_table[0][0] = 1-head_prob[0]

    for i in range(1, N):
        for j in range(i+2):
            head_prob_table[i][j] += head_prob_table[i-1][j] * (1 - head_prob[i])
            if j > 0:
                head_prob_table[i][j] += head_prob_table[i-1][j-1] * head_prob[i]

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

if __name__ == '__main__':
    main()

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

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

Solution (Python):
N = int(input())
def main():
    head_prob_table = [[0.0] * (N+1) for i in range(N)]
    head_prob = list(map(float, input().split()))

    head_prob_table[0][1] = head_prob[0]
    head_prob_table[0][0] = 1-head_prob[0]

    for i in range(1, N):
        for j in range(i+2):
            head_prob_table[i][j] += head_prob_table[i-1][j] * (1 - head_prob[i])
            if j > 0:
                head_prob_table[i][j] += head_prob_table[i-1][j-1] * head_prob[i]

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

if __name__ == '__main__':
    main()

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