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

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

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

print(num)

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

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

print(num)

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

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

print(num)

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

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

print(num)

Solution (Python):
import sys


input = sys.stdin.readline

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

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

    for i in range(N):
        p_head = p[i]
        p_tail = 1 - p[i]
        dp = [dp[j -1] * p_head + dp[j] * p_tail for j in range(N+1)]
    
    ans = sum(dp[(N//2+1):])

    print(ans)

main()

Solution (Python):

import sys
input = sys.stdin.readline

def f2(n, p):
    dp = [ 0.0 ] * (n + 1)
    dp[0] = 1.0
    
    for i in range(n):
        dp_ = list(dp)
        pi_ = 1 - p[i]
        for j in range(n + 1):
            dp[j] = dp_[j - 1] * p[i] + dp_[j] * pi_
        
    return(sum(dp[n // 2 + 1:]))

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

Solution (Python):
import sys


input = sys.stdin.readline

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

    print(ans)

main()

Solution (Python):


import math

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

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

    for i, pr in enumerate(ps, start=1):
        for j in range(N+1):
            dp[i][j] = dp[i-1][j] * (1 - pr)
            if j:
                dp[i][j] += dp[i-1][j-1] * pr

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


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np

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

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

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

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

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

N = int(input())
pn = list(map(float,input().split()))
dp = np.array([0.0] * (N+1))
dp[0] = 1.0
for i in range(N):
    tmp = dp * (1-pn[i])
    tmp[1:] += dp[:-1] * pn[i]
    dp = tmp

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

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

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
P=tuple(map(float,input().split()))
DP=[[0.0]*(n+1) for _ in range(n+1)]
DP[0][0]=1.0
for i in range(1,n+1):
    for j in range(i+1):
        DP[i][j]=DP[i-1][j]*(1-P[i-1])
        if j:
            DP[i][j]+=DP[i-1][j-1]*P[i-1]
ans=0.0
for i in range(n//2+1,n+1):
    ans+=DP[-1][i]
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
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])
        if j:
            DP[i][j]+=DP[i-1][j-1]*P[i-1]
ans=0
for i in range(n//2+1,n+1):
    ans+=DP[-1][i]
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
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):
    DP[i][0]=DP[i-1][0]*(1-P[i-1])
for i in range(1,n+1):
    for j in range(1,i+1):
        DP[i][j]=DP[i-1][j-1]*P[i-1]+DP[i-1][j]*(1-P[i-1])
ans=0
for i in range(n//2+1,n+1):
    ans+=DP[-1][i]
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
P=tuple(map(float,input().split()))
DP=[[0]*(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,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//2+1])

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):
    DP[i][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-1][j]*(1-P[i-1])
print(DP[n][n//2+1])

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007


def A():
    """
    N個の足場があります。足場には1,2,…,Nと番号が振られています。 
    各i (1≤i≤N) について、足場 i の高さは hi です。
    最初、足場 1 にカエルがいます。 カエルは次の行動を何回か繰り返し、足場 N まで辿り着こうとしています。
    足場 i にいるとき、足場 i+1 または i+2 へジャンプする。
    このとき、ジャンプ先の足場を j とすると、コスト |hi−hj| を支払う。
    カエルが足場 N に辿り着くまでに支払うコストの総和の最小値を求めてください。

    制約
        入力はすべて整数である。
    2≤N≤10**5
    1≤hi≤10**4
    """
    n = II()
    h = LI()
    dp = [0 for i in range(n)]
    dp[1] = abs(h[0] - h[1])
    for i in range(2,n):
        dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]))
    print(dp[n-1])
    return


def B():
    n, K = LI()
    h = LI()
    dp = [float("INF") for i in range(n + K + 1)]
    dp[0] = 0
    for i in range(n):
        for k in range(1, K + 1):
            if i + k >= n:
                break
            dp[i + k] = min(dp[i + k], dp[i] + abs(h[i] - h[i + k]))
    print(dp[n-1])
    return


def C():
    n = II()
    abc = LIR(n)
    dp = [0 for i in range(3 * n + 1)]
    dp[0] = abc[0][0]
    dp[1] = abc[0][1]
    dp[2] = abc[0][2]
    for i in range(1,n):
        dp[3 * i] = max(dp[3 * i], dp[3 * (i - 1) + 1] + abc[i][0], dp[3 * (i - 1) + 2] + abc[i][0])
        dp[3 * i + 1] = max(dp[3 * i + 1], dp[3 * (i - 1) + 2] + abc[i][1], dp[3 * (i - 1)] + abc[i][1])
        dp[3 * i + 2] = max(dp[3 * i + 2], dp[3 * (i - 1) + 1] + abc[i][2], dp[3 * (i - 1)] + abc[i][2])
    dp[3 * n] = max(dp)
    print(dp[3*n])

    return


def D():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**5
    1≤wi≤W
    1≤vi≤10**9"""
    n, w = LI()
    wv = LIR(n)
    dp = [[0 for k in range(w + 1)] for i in range(n + 2)]
    for i in range(1,n + 1):
        for j in range(w + 1):
            if j < wv[i-1][0]:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - wv[i - 1][0]] + wv[i - 1][1])
    print(dp[n+1][w])

    
    return


def E():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**9
    1≤wi≤W
    1≤vi≤10**3"""
    n, w = LI()
    wv = LIR(n)
    dp = [[float("INF") for i in range(10 ** 5 + 1)] for k in range(n + 1)]
    dp[0][0] = 0
    for i in range(n):
        for k in range(10 ** 5 + 1):
            if k < wv[i][1]:
                dp[i + 1][k] = dp[i][k]
            else:
                dp[i + 1][k] = min(dp[i][k], dp[i][k - wv[i][1]] + wv[i][0])
    ans = 0
    for i in range(10 ** 5 + 1):
        if dp[n][i] <= w:
            ans = i
    print(ans)

    return


def F():
    s = "abc"*1000
    t = "abc"*1000
    dp = [[0 for i in range(len(t)+1)] for k in range(len(s)+1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                if dp[i][j + 1] < dp[i + 1][j]:
                    dp[i + 1][j + 1] = dp[i + 1][j]
                else:
                    dp[i + 1][j + 1] = dp[i][j + 1]
        
    print(dp[len(s)][len(t)])
    return


def G():
    n, m = LI()
    xy = LIR_(m)
    edge = [[] for i in range(n)]
    for x,y in xy:
        edge[x].append(y)
    dp = [0 for i in range(n)]
    def ans(dp, i):
        
        if dp[i] != 0:
            return dp[i]
        else:
            if len(edge[i]) == 0:
                return 0
            ansb = 0
            for k in edge[i]:
                
                ansb = max(ansb, ans(dp, k) + 1)
                dp[i] = max(ansb, dp[i])
                
            return ansb
            
    for i in range(n):
        dp[i] = ans(dp, i)
    print(max(dp))
    return


def H():
    h, w = LI()
    a = SR(h)
    dp = [[0 for i in range(w)] for k in range(h)]
    for i in range(w):
        if a[0][i] == "
            break
        dp[0][i] = 1
    for i in range(h):
        if a[i][0] == "
            break
        dp[i][0] = 1
    for i in range(1,w):
        for k in range(1, h):
            
            if a[k - 1][i] == ".":
                if a[k][i - 1] == ".":
                    dp[k][i] = dp[k - 1][i] + dp[k][i - 1] % mod
                else:
                    dp[k][i] = dp[k - 1][i]
            else:
                if a[k][i - 1] == ".":
                    dp[k][i] = dp[k][i - 1]
    print(dp[h-1][w-1] % mod)

    return


def I():
    n = II()
    p = LF()
    dp = [[0 for k 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):
        for k in range(i + 1):
            if k == 0:
                
                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])
    
    print(sum(dp[n][n//2+1:]))
    return 
























if __name__ == '__main__':
    I()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007


def A():
    n = I()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n-2):
        dp[i+1] = min(dp[i+1],dp[i]+abs(h[i+1]-h[i]))
        dp[i+2] = min(dp[i+2],dp[i]+abs(h[i+2]-h[i]))
    dp[n-1] = min(dp[n-1],dp[n-2]+abs(h[n-1]-h[n-2]))
    print(dp[n-1])

def B():
    n,k = LI()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n):
        for j in range(1,min(n-i,k+1)):
            dp[i+j] = min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
    print(dp[n-1])


def C():
    n = I()
    v = LIR(n)
    dp = [[0,0,0] for i in range(n+1)]
    for i in range(n):
        dp[i+1][0] = max(dp[i+1][0],dp[i][1]+v[i][0],dp[i][2]+v[i][0])
        dp[i+1][1] = max(dp[i+1][1],dp[i][2]+v[i][1],dp[i][0]+v[i][1])
        dp[i+1][2] = max(dp[i+1][2],dp[i][0]+v[i][2],dp[i][1]+v[i][2])
    print(max(dp[n]))


def D():
    n,W = LI()
    g = LIR(n)
    dp = [[0 for i in range(W+1)] for j in range(n+1)]
    for i in range(n):
        for j in range(W+1)[::-1]:
            w,v = g[i]
            if j >= w:
                dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
            else:
                dp[i+1][j] = max(dp[i+1][j],dp[i][j])
    print(max(dp[n]))

def E():
    n,W = LI()
    g = LIR(n)
    V = 100000
    dp = [[float("inf") for i in range(V+1)] for j in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(V+1)[::-1]:
            w,v = g[i]
            if j >= v:
                dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)
            else:
                dp[i+1][j] = min(dp[i+1][j],dp[i][j])

    for i in range(V+1)[::-1]:
        if dp[n][i] <= W:
            print(i)
            quit()


def F():
    s = S()
    t = S()
    dp = [[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i+1][j+1] = max(dp[i][j]+1,dp[i+1][j],dp[i][j+1])
            else:
                dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])

    i = len(s)
    j = len(t)
    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:
            i -= 1
            j -= 1
            ans = s[i]+ans
    print(ans)

def G():
    n,m = LI()
    e = LIR(m)
    dp = [0 for j in range(m+1)]
    for i in range(m):
        x,y = e[i]
        dp[i+1][y] = max(dp[i][y],dp[i][x]+1)
    ans = 0
    for i in range(m+1):
        ans = max(dp[i])
    print(ans)

def H():
    h,w = LI()
    s = SR(h)
    dp = [[0 for i in range(w)] for j in range(h)]
    dp[0][0] = 1
    for i in range(h-1):
        for j in range(w-1):
            if s[i+1][j] == ".":
                dp[i+1][j] += dp[i][j]
                dp[i+1][j] %= mod
            if s[i][j+1] == ".":
                dp[i][j+1] += dp[i][j]
                dp[i][j+1] %= mod
    for j in range(w-1):
        if s[h-1][j+1] == ".":
            dp[h-1][j+1] += dp[h-1][j]
            dp[h-1][j+1] %= mod
    for i in range(h-1):
        if s[i+1][w-1] == ".":
            dp[i+1][w-1] += dp[i][w-1]
            dp[i+1][w-1] %= mod
    print(dp[h-1][w-1])


def J():
    n = I()
    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 i in range(n):
        for j in range(n+1):
            dp[i+1][j] = p[i]*dp[i][j-1]+(1-p[i])*dp[i][j]

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

if __name__ == "__main__":
    J()

Solution (Python):



import sys


n = int(input())
p = list(map(float, sys.stdin.readline().rstrip().split()))

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

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

Solution (Python):
import numpy as np
n = int(input())
g = 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*g[i],1) + dp*(1-g[i])
print(sum(dp[n//2+1:]))

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

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

Solution (Python):


import sys
input = sys.stdin.readline

def f3(n, p):
    dp = [ 0.0 ] * (n + 1)
    dp[0] = 1.0
    for i in range(n):
        pi_ = 1 - p[i]
        dp = [dp[j - 1] * p[i] + dp[j] * pi_ \
            for j in range(n + 1)]
    return(sum(dp[n // 2 + 1:]))

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

Solution (Python):

import sys
input = sys.stdin.readline

def f2(n, p):
    dp = [ 0.0 ] * (n + 1)
    dp[0] = 1.0
    
    for i in range(n):
        dp_ = list(dp)
        pi_ = 1 - p[i]
        for j in range(n + 1):
            dp[j] = dp_[j - 1] * p[i] + dp_[j] * pi_
        
    return(sum(dp[n // 2 + 1:]))

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

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

Solution (Python):
"""
I - Coins

考え方:
    N 枚のコインを投げた時, n 枚表になる確率を求める.
    以下の二つの和で求められる(①).
        N - 1 枚投げた時に n - 1 枚表になり, さらに次に投げた時に表になる確率
        N - 1 枚投げた時に n 枚表になり, さらに次に投げた時に裏になる確率
    N を0から始めるとDPで求められる.
    0 <= n <= N / 2 となるすべての n の確立の和が表が半分以下となる確率 X.
    表が半分以上となる(裏より多くなる)確率は 1 - X.
    計算量は O(n^2) <- あってる？？
"""


def solve():
    N = int(input())
    P = [float(i) for i in input().split()]
    dp = [1 for i in range(int((N + 1) / 2))]  
    for i, p in enumerate(P, 1):
        for j in reversed(range(len(dp))):
            if i <= j:
                
                dp[j] *= p
            elif j == 0:
                
                dp[j] *= (1 - p)
            else:
                
                dp[j] = dp[j] * (1 - p) + dp[j - 1] * p
    print(1 - sum(dp))


if __name__ == '__main__':
    solve()

Solution (Python):
import sys,bisect
input = sys.stdin.readline
n = int(input())
p = tuple(map(float,input().split()))

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

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

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

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

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

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

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

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

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

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

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




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

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

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

print(res)

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

Solution (Python):

from __future__ import division, print_function

import os
import sys
from atexit import register
from io import BytesIO

range = xrange

sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))

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

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

dp = [0.0] * (n + 1)
dp[0], dp[1] = 1 - p[0], p[0]

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

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

Solution (Python):

"""
This file is part of https://github.com/cheran-senthil/PyRival
Copyright 2019 Cheran Senthilkumar <hello@cheran.io>

"""
from __future__ import division, print_function

import itertools
import math
import os
import sys
from atexit import register
from io import BytesIO


class dict(dict):
    """dict() -> new empty dictionary"""

    def items(self):
        """D.items() -> a set-like object providing a view on D's items"""
        return dict.iteritems(self)

    def keys(self):
        """D.keys() -> a set-like object providing a view on D's keys"""
        return dict.iterkeys(self)

    def values(self):
        """D.values() -> an object providing a view on D's values"""
        return dict.itervalues(self)


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


range = xrange

filter = itertools.ifilter
map = itertools.imap
zip = itertools.izip

sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))

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

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

dp = [[0.0] * (n + 1) for _ in range(n)]
dp[0][0], dp[0][1] = 1 - p[0], p[0]

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

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

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

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

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

DP = [[0] * (n+1) for j in range(n+1)]
DP[0][0] = 1

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

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

Solution (Python):
import numpy as np

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

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

for i in P:
    tmp = dp * (1-i)
    
    tmp[1:] += dp[:-1] * i
    dp = tmp

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

Solution (Python):


import sys
import numpy as np

INF = float('inf')
MOD = 10 ** 9 + 7

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 II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    P = LF()

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

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

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


print(main())

Solution (Python):


import sys

INF = float('inf')
MOD = 10 ** 9 + 7

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 II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    P = LF()

    
    dp = [1]

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

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


print(main())

Solution (Python):


import sys

INF = float('inf')
MOD = 10 ** 9 + 7

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 II(): return int(sys.stdin.readline())
def SI(): return input()


n = II()
P = LF()


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



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

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

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

print(ans)

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

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) for _ in range(n+1)]

dp[0][0] = 1
for o in range(n):
    for u in range(n):
        if o+u >= n:
            continue
        
        dp[o][u+1] += (1-p[o+u]) * dp[o][u]
        dp[o+1][u] += p[o+u] * dp[o][u]
        
ans = 0
for o in range(n+1):
    u = n-o
    if o > u:
        ans += dp[o][u]
        
print(ans)

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

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

m = (len(dp[-1])+1) // 2
print(sum(dp[-1][m:]))