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())
coin_list = [ float(v) for v in input().split() ]
probability_list = [1]

for i in coin_list:
    l = len(probability_list)
    new_probability_list = [0] * (l+2)
    for j in range(l):
        new_probability_list[j] += probability_list[j] * (1-i)
        new_probability_list[j+2] += probability_list[j] * i
    probability_list = new_probability_list

print(sum(probability_list[l//2+2:]))

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

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

Solution (Python):
def solve():
    p = read()
    result = think(p)
    write(result)


def read():
    n = read_int(1)[0]
    return read_float(n)


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_float(n):
    return list(map(lambda x: float(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(p):
    n = len(p)

    
    

    accumulated = [[0.0 for x in range(n + 1)] for y in range(n)]
    accumulated[0][0] = 1.0 - p[0]
    accumulated[0][1] = p[0]

    for ith, each_p in enumerate(p):
        if ith == 0:
            continue
        for face_count in range(ith + 2):
            if face_count == 0:
                accumulated[ith][face_count] = accumulated[ith - 1][face_count] * (1.0 - each_p)
            elif face_count == ith + 1:
                accumulated[ith][face_count] = accumulated[ith - 1][face_count - 1] * each_p
            else:
                accumulated[ith][face_count] = accumulated[ith - 1][face_count] * (1.0 - each_p) + accumulated[ith - 1][face_count - 1] * each_p

    return sum(accumulated[n - 1][((n + 1) // 2):])


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

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

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

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

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

dp = [[0] * (N * 2 + 3) for _ in range(2)]
def pos(i):
    return i + N + 1
dp[0][pos(0)] = 1
for i in range(1, len(ps) + 1):
    d = i % 2
    dm = (i - 1) % 2
    for j in range(-i, i + 1):
        dp[d][pos(j)] = dp[dm][pos(j-1)] * ps[i-1] + dp[dm][pos(j+1)] * (1.0 - ps[i-1])

s = 0
for i in range(1, N+1):
    s += dp[N%2][pos(i)]
print(s)

Solution (Python):
import numpy as np

N = int(input())
inputs = np.array([float(i) for i in input().split()])

dp = np.array([np.array([0.0 for _ in range(N+1)]) for _ in range(N+1)])
dp[1][0] = 1 - inputs[0]
dp[1][1] = inputs[0]
for i in range(2, N+1):
    dp[i][1:] = dp[i-1][1:] * (1.0 - inputs[i-1]) + dp[i-1][:N] * inputs[i-1]
    dp[i][0] = dp[i-1][0] * (1.0 - inputs[i-1])

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

Solution (Python):
n = int(input())
a = list(map(float,input().split()))
b = [0]
table = [[0 for _ in range(n+1)]for  _ in range(n+1)]
table[0][0] = 1
for v in a:
    b.append(1-v)
s1 =1
s2 =1
ans = 0
a = [0]+a
for i in range(1,n+1):
    s1*=a[i]
    s2*=b[i]
    table[i][0]=s1
    table[0][i]=s2
for i in range(1,n):
    for j in range(1,n):
        if i+j<=n:
            table[i][j] = table[i-1][j]*a[i+j]+ table[i][j-1]*b[i+j]
for i in range(n+1):
    for j in range(n+1):
        if i>j and i+j ==n:
            ans+= table[i][j]
print(ans)

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

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

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

Solution (Python):



import sys
sys.setrecursionlimit(10000000)
def LI(): return list(map(float,sys.stdin.readline().split()))
def LIR(n): return [LI() for _ in range(n)]
mod = 10**9+7

def I():
    n = int(input())
    p = 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(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:n+1]))





if __name__ == '__main__':
    I()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N = I()
p = LF()

dp = [[0.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+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):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

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

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

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

Solution (Python):
from __future__ import division, print_function
def main():
    n=int(input())
    l1=list(map(float,input().split()))
    dp=[ [0]*(n+1) for _ in range(n) ]
    dp[0][0]=l1[0]
    dp[0][1]=1-l1[0]
    for i in range(1,n):
        for j in range(i+2):
            if j>0:
                dp[i][j]=dp[i-1][j]*(l1[i])+dp[i-1][j-1]*(1-l1[i])
            else :
                dp[i][j]=dp[i-1][j]*(l1[i])
    if n%2==1:
        x=n//2
    else :
        x=n//2-1
    print(sum(dp[n-1][:x+1]))











py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
sys.setrecursionlimit(10**5)
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

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

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            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')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')


import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'


def readnumbers(zero = 0):
    conv = ord if py2 else lambda x:x
    A = []; numb = zero; sign = 1; i = 0; s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'0' [0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-' [0]: sign = -1
            elif s[i] != b'\r' [0]:
                A.append(sign*numb)
                numb = zero; sign = 1
            i += 1
    except:pass
    if s and s[-1] >= b'0' [0]:
        A.append(sign*numb)
    return A

if __name__== "__main__":
  main()

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

memo[0][0] = 1 - P[0]
memo[0][1] = P[0]

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

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

import functools
import operator
n = int(input())
p = list(map(float, input().split()))
half = n // 2 + 1

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


















for i in range(0, n + 1):
    for depth in range(-1, n):
        if depth == -1:
            dp[i][depth] = 0
        elif i == 0:
            dp[i][depth] = functools.reduce(operator.mul, map(lambda x: 1 - x, p[:depth + 1]))
        elif (i - 1) == depth:
            dp[i][depth] = functools.reduce(operator.mul, p[:depth + 1])
        else:
            dp[i][depth] = dp[i - 1][depth - 1] * p[depth] + dp[i][depth - 1] * (1 - p[depth])

print(sum(dp[i][n - 1] for i in range(half, n + 1)))

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

import functools
import operator
n = int(input())
p = list(map(float, input().split()))
half = n // 2 + 1

dp = [[None] * (n + 1) for _ in range(n + 1)]
def dfs(n=half, depth=n - 1):
    if depth < 0:
        return 0

    if dp[n][depth] is not None:
        return dp[n][depth]

    if n == 0:
        r = functools.reduce(operator.mul, map(lambda x: 1 - x, p[:depth + 1]))
    elif (n - 1) == depth:
        r = functools.reduce(operator.mul, p[:depth + 1])
    else:
        r = dfs(n - 1, depth - 1) * p[depth] + dfs(n, depth - 1) * (1 - p[depth])
    dp[n][depth] = r
    return r

print(sum(dfs(i) for i in range(half, n + 1)))

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

import functools
import operator
n = int(input())
p = list(map(float, input().split()))
half = n // 2 + 1

dp = [[None] * (n + 1) for _ in range(n + 1)]
def dfs(n=half, depth=n - 1):
    if depth < 0 or (n - 1) > depth:
        return 0

    if dp[n][depth] is not None:
        return dp[n][depth]

    if n == 0:
        r = functools.reduce(operator.mul, map(lambda x: 1 - x, p[:depth + 1]))
    elif (n - 1) == depth:
        r = functools.reduce(operator.mul, p[:depth + 1])
    else:
        r = dfs(n - 1, depth - 1) * p[depth] + dfs(n, depth - 1) * (1 - p[depth])
    dp[n][depth] = r
    return r

print(sum(dfs(i) for i in range(half, n + 1)))

Solution (Python):


import sys

class ICoins:
    def solve(self):
        n = int(input())
        p = [float(_) for _ in input().split()]
        dp = [0.0] * (n + 1)
        
        dp[0] = 1
        for j in range(1, n + 1):
            for i in range(j, 0, -1):
                dp[i] = dp[i] * (1 - p[j - 1]) + dp[i - 1] * p[j - 1]
            dp[0] = dp[0] * (1 - p[j - 1])
        ans = 0
        for i in range(n + 1):
            if i > n - i:
                ans += dp[i]
        print(ans)


solver = ICoins()
input = sys.stdin.readline

solver.solve()

Solution (Python):


import sys

class ICoins:
    def solve(self):
        n = int(input())
        p = [float(_) for _ in input().split()]
        dp = [[0.0] * (n + 1) for _ in range(n + 1)]
        
        dp[0][0] = 1
        for j in range(1, n + 1):
            for i in range(j + 1):
                dp[i][j] = dp[i][j - 1] * (1 - p[j - 1])
                if i > 0:
                    dp[i][j] += dp[i - 1][j - 1] * p[j - 1]

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


solver = ICoins()
input = sys.stdin.readline

solver.solve()

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

Solution (Python):
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)

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

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

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

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

Solution (Python):
n = int(raw_input())
a = list(map(float, raw_input().split()))
 
dp = [[0]*(n+1) for i in xrange(n+1)]
dp[0][0] = 1
 
for i in xrange(1,n+1):
  dp[0][i] = 0
  dp[i][0] = dp[i-1][0] * (1 - a[i-1])
  
for i in xrange(1, n+1):
  for j in xrange(1, n+1):
    dp[i][j] = dp[i-1][j-1] * a[i-1] + dp[i-1][j] * (1 - a[i-1])
ans = 0
for i in xrange(n // 2 + 1 , n+1):
  ans += dp[n][i]

print ans

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

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

Solution (Python):
N = int(input())
P = [0]
P.extend(map(float, input().split()))

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()
INL=list(map(float, LS()))
DP=[0.0]*(N+1)
DP[0]=1.0

for p in INL:
    for i in reversed(range(N)):
        DP[i+1] = DP[i+1]*(1.0-p) + DP[i]*p


print(DP[N//2+1])

Solution (Python):
from subprocess import*
call(('pypy3','-c',"""
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):
n=int(input())
P=[float(i) for i in input().split()]
Ans=[[0]*(n+1) for _ in range(n+1)]
Ans[0][0]=1
for i in range(1,n+1):
  for j in range(i+1):
    if j==0:
      Ans[i][j]=Ans[i-1][j]*(1-P[i-1])
    else:
      Ans[i][j]=Ans[i-1][j]*(1-P[i-1])+Ans[i-1][j-1]*P[i-1]
ans=0
for i in range(n//2+1):
  ans+=Ans[n][i]
print(1-ans)

Solution (Python):

import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, p: "List[float]"):
    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] += p[i] * dp[i][j]
            dp[i+1][j] += (1.0 - p[i]) * dp[i][j]
    return sum(dp[-1][(N // 2 + 1):])


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) ]  
    result = solve(N, p)
    print(result)

if __name__ == '__main__':
    main()

Solution (Python):
input()
a=[1] 
for i in input().split():
  a=[x+(y-x)*float(i) for x,y in zip(a+[0],[0]+a)]
print(sum(a[len(a)//2:]))

Solution (Python):
import fileinput

def heads_win_proba(probs_list):
    prev_head_probs = [1.0]
    for coin_count, prob in enumerate(probs_list):
        coin_count += 1
        current_head_porbs = [0.0] * (coin_count + 1)
        for head_count in range(coin_count + 1):
            if head_count < coin_count:
                current_head_porbs[head_count] = prev_head_probs[head_count] * (1.0 - prob)
            if head_count > 0:
                current_head_porbs[head_count] += prev_head_probs[head_count - 1] * prob
        prev_head_probs = current_head_porbs
    return sum(prev_head_probs[len(prev_head_probs) // 2:])

inp = fileinput.FileInput()
coin_count = int(inp.readline())
prob_list = [float(n) for n in inp.readline().split(" ")]
print(heads_win_proba(prob_list))

Solution (Python):



import numpy as np


def get_inputs():
    
    

    N = int(input())

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

    return N, ps









N, ps = get_inputs()


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

dp[0][1] = float(ps[0])
dp[0][0] = float(1.0 - ps[0])

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

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

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

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

n = int(input())
f(n)

Solution (Python):
from collections import Counter
N = int(input())
P = map(float, input().split())
dp = Counter()
dp[0] = 1
for p in P:
    dp1 = Counter()
    for k, v in dp.copy().items():
        dp1[k] += v*(1 - p)
        dp1[k+1] += v*p 
    dp = dp1.copy()
print(sum(v for k, v in dp.items() if 2*k > N))

Solution (Python):


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

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


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

Solution (Python):
import numpy as np

n = int(input())
arr = list(map(float, input().split()))
dp = np.zeros(n + 1, dtype=float)
dp[0] = 1.0

for p in arr:
    tmp = dp * (1 - p)
    tmp[1:] += dp[:-1] * p
    dp = tmp

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

Solution (Python):


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

dp = [[1 if k == 0 else 0 for k in range(N+1)] for _ in range(N+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(dp[N][(N+1)//2])

Solution (Python):



def update(i, k):
    if k == 0:
        dp[i][k] = dp[i-1][0] * (1-P[i-1])
    elif k == i:
        dp[i][k] = dp[i-1][k-1] * P[i-1]
    else:
        dp[i][k] = dp[i-1][k-1] * P[i-1] + dp[i-1][k] * (1-P[i-1])


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

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

for i in range(1, N+1):
    for k in range(i+1):
        update(i, k)

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

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

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

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

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

Solution (Python):
n=int(input())
arr=list(map(float,input().split()))
dp=[0.0]*(n+1)
dp[0]=1.0
for i in range(n):
    p=arr[i]
    for j in range(i+1,-1,-1):
        if j==0:
            dp[j]=(1-p)*(dp[j])
        else:
            dp[j]=((p)*dp[j-1])+((1-p)*dp[j])
ans=0
for heads in range(n+1):
    tails=n-heads
    if heads>tails:
        ans+=dp[heads]
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def INT_(n): return int(n)-1


def MI(): return map(int, input().split())


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [input() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    N = I()
    p = LF()
    
    dp = [[0] * (N+1) for _ in range(N)]
    dp[0][1] = p[0]
    dp[0][0] = 1-p[0]
    for i in range(1, N):
        for k in range(i+2):
            if k != 0:
                dp[i][k] += dp[i - 1][k - 1] * p[i]
            if k <= i:
                dp[i][k] += dp[i-1][k]*(1-p[i])
    ans = 0
    for i in range((N + 1) // 2, N + 1):
        ans += dp[N - 1][i]
    
    print(ans)


if __name__ == '__main__':
    main()

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

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

dp = [[0.0] * (len(v)+1) for i in range(len(v))]
for x in range(n):
	for a in range(x + 2):
		if x == 0 and a == 0:
			dp[x][a]=v[x]
		elif x == 0 and a == 1 and n != 1:
			dp[x][a]=1-v[x]
		elif a > n/2:
			dp[x][a]=dp[x-1][a]*v[x]
		else:
			dp[x][a]=dp[x-1][a]*v[x]+dp[x-1][a-1]*(1-v[x])


print(sum(dp[n-1]))

Solution (Python):
inp = lambda cast=int: list(map(cast, input().split()))

n, = inp()
A = [0.0] + inp(float)
dp = [[0.0 for _ in range(n + 1)] for _ in range(n + 1)]
res = 0.0
for i in range(n + 1):
    for j in range(n + 1):
        if i == 0:
            dp[i][j] = 1 if j == 0 else 0
        elif j == 0:
            dp[i][j] = dp[i-1][j] * (1 - A[i])
        else:
            dp[i][j] = dp[i-1][j] * (1 - A[i]) \
                       + dp[i-1][j-1] * A[i]
        if i == n and j > n/2:
            res += dp[i][j]
print(res)

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

Solution (Python):
from itertools import accumulate
from math import*
from collections import deque
from collections import defaultdict
from itertools import permutations
from heapq import*
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

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

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

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

Solution (Python):



import numpy as np

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

dp = np.zeros((N+2, N+1))

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

Solution (Python):
import numpy as np
from sys import stdin


def dp_solve(n):
    dp = np.zeros(n+1)
    dp[0] = 1
    pi = list(map(float, stdin.readline().split()))

    for i, p in enumerate(pi):
        dp[1:] = dp[1:]*(1-pi[i]) + dp[:n]*pi[i]
        dp[0] = dp[0]*(1-pi[i])
    return dp


if __name__ == "__main__":
    n = int(input())
    res = dp_solve(n)
    print(sum(res[n//2+1:]))

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


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


dp[0][0] = 1


for t_i in range(N):
    for o_i in range(N + 1):
        if dp[o_i][t_i] == 0:
            continue

        
        dp[o_i][t_i + 1] += dp[o_i][t_i] * (1-P[t_i])
        
        dp[o_i + 1][t_i + 1] += dp[o_i][t_i] * P[t_i]


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

print(ans)

Solution (Python):
def func(num,arr):
  dp=[1]*(n+1)
  dp[0]=(1-arr[0])
  dp[1]=arr[0]
  for i in range(1,n):
    p0=arr[i]
    p1=1-arr[i]
    dp[i+1]=dp[i]*p0
    for j in range(1,i+1):
      dp[i+1-j]=dp[i-j]*p0+dp[i+1-j]*p1
    dp[0]=dp[0]*p1
  return dp

n=int(input())
arr=[float(s) for s in input().split()]
dp=func(n,arr)
ans=0
for i in range(int(n/2)+1,n+1):
  ans+=dp[i]
print(ans)

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

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

Solution (Python):
"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_i

I - Coins

"""
import collections


def solve(ps):
    dp = collections.defaultdict(float)
    dp[0] = 1.0
    for p_i in ps:
        for head_count in reversed(range(N + 1)):
            dp[head_count] = p_i * dp[head_count - 1] + (1 - p_i) * dp[head_count]

    more_than_half = (N + 2) // 2
    res = sum(dp[head_count] for head_count in range(more_than_half, N + 1))
    return res
 

N = int(input())
ps = [float(s) for s in input().split()]
res = solve(ps)
print(res)

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

Solution (Python):
import numpy as np

n=int(input())
ps=list(map(float,input().split()))
lim=(n+1)//2
dp=np.zeros(lim+1,dtype=np.float64)
dp[0]=1
for p in ps:
    dp[lim]=dp[lim]+dp[lim-1]*p
    dp[1:lim]=dp[:lim-1]*p+dp[1:lim]*(1-p)
    dp[0]=dp[0]*(1-p)
print(dp[-1])

Solution (Python):
n=int(input())
ps=list(map(float,input().split()))
lim=(n+1)//2
dp=[0]*(lim+1)
dp[0]=1
for pi,p in enumerate(ps):
    if pi+1>=lim:
        st=lim-1
        dp[lim]=dp[lim]+dp[lim-1]*p
    else:
        st=pi+1
    for i in range(st,0,-1):
        dp[i]=dp[i-1]*p+dp[i]*(1-p)
    dp[0]=dp[0]*(1-p)
print(dp[-1])