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



Sample input:
3
0.30 0.60 0.80


Sample output:
0.612

Submission status: Accepted

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N = gete(int)
    # p = tuple(geta(lambda s: int(s.decode()[2:])))
    p = tuple(geta(float))

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

    for i, pi in enumerate(p, 1):
        qi = 1 - pi
        dpi = dp[i]
        dpi1 = dp[i - 1]

        dpi[0] = dpi1[0] * qi

        for j in range(1, i + 1):
            dpi[j] = dpi1[j - 1] * pi + dpi1[j] * qi

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    p = tuple(map(float, input().split()))
    # pr = [1 - pi for pi in p]
    # DPの二次元配列を行i1＝コインの枚数、列i2＝表がでたコインの枚数、で構築する。
    # DP[][]の初期値は0。ただし0列(表が0枚になる確率)をまず初期化する。
    # DP[i1][i2]の値は、DP[i1-1][i2] * pr + DP[i1-1][i2-1] * p
    # 「表の枚数＞裏の枚数になる確率」は、DPの最下行のX列から右の列の価の合計。
    dp = [[0.0] * (n + 1) for _ in range(n + 1)]
    # ０列目を初期化する。
    dp[0][0] = 1.0 #コイン0枚目で表が０枚の確率＝１
    for i0 in range(1, n + 1):
        dp[i0][0] = dp[i0-1][0] * (1 - p[i0-1])

    for i1 in range(1, n + 1):
        pe = p[i1 - 1]
        pre = 1 - pe
        for i2 in range(1, i1 + 1):
            dp[i1][i2] = dp[i1-1][i2] * pre + dp[i1-1][i2-1] * pe

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
mod = pow(10, 9) + 7
mod2 = 998244353
inf = int(1e20)
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(" ".join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


n = int(data())
arr = list(map(float, data().strip().split()))
dp = dd(lambda: dd(float))
dp[0][0] = 1
for i in range(1, n+1):
    dp[i][0] = dp[i-1][0] * (1.0 - arr[i-1])
answer = 0.0
for i in range(1, n+1):
    for j in range(1, n+1):
        dp[i][j] = arr[i-1] * dp[i-1][j-1] + (1.0 - arr[i-1]) * dp[i-1][j]
        if j >= n//2+1 and i == n:
            answer += dp[i][j]
out(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, p: "List[float]"):
    dp = [[0] * (N+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(1, N+1):
        for j in range(i+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 j in range(N//2+1, N+1):
        res += dp[N][j]
    print(res)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    p = [float(next(tokens)) for _ in range(N)]  # type: "List[float]"
    solve(N, p)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

x=int(n/2)
x=n-x
ans=0

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


print(ans)

Submission status: Accepted

Solution code:
n=int(input())
h=list(map(float,input().split()))
t=[]
for i in range(n+1):
    temp=[1]*(n+1)
    t.append(temp)
for i in range(1,n+1):
    for j in range(i+1):
        if j==0:
            t[i][j]=t[i-1][0]*(1-h[i-1])
        elif i==j:
            t[i][j]=t[i-1][j-1]*(h[i-1])
        else:
            t[i][j]=(t[i-1][j-1]*(h[i-1]))+(t[i-1][j]*(1-h[i-1]))
a=0
for i in range(n//2+1,n+1):
    a+=t[n][i]
print(a)

Submission status: Accepted

Solution code:

    

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

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2000)
input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(float, input().split())
LIN=lambda : list(IN())
mod=1000000007

#+++++

def main():
	n = int(input())
	#b , c = IN()
	#s = input()
	al = LIN()
	#p[i][j]は、i番目までにj枚が表になっている確率をあらわす。
	p = [[0]*(n+1) for _ in range(n+1)]
	p[0][0]=1
	for i in range(1, n+1):
		for j in range(n+1):
			omote = al[i-1]
			ura = 1 - omote
			p[i][j] += p[i-1][j]*ura
			if j > 0:
				p[i][j] += p[i-1][j-1]*omote
	k = p[-1][(n+1)//2:]
	#pa(k)
	r = sum(k)
	print(r)


memo_s=[]
al=[1,1]
n=1
def cc(state, maisuu):
	nokori = n-state
	if maisuu==0:
		return 1
	if nokori < maisuu:
		return 0
	global memo_s
	k = memo_s[state][maisuu]
	if k >= 0:
		return k
	
	omote = al[state]
	ura = 1-omote
	r = cc(state+1, maisuu-1)*omote
	r += cc(state+1, maisuu)*ura
	
	memo_s[state][maisuu]=r
	return r
	
def main2():
	global n
	n = int(input())
	global memo_s
	memo_s = [[-1]*(n+1) for _ in range(n+1)]
	
	v = LIN()
	global al
	al=v[:]
	
	r = cc(0, (n+1)//2)
	print(r)
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    dp = [0] * (n + 1)
    dp[0] = 1
    for p in map(float, input().split()):
        ndp = [0] * (n + 1)
        for i in range(n):
            ndp[i + 1] += dp[i] * p
        for i in range(n):
            ndp[i] += dp[i] * (1 - p)
        dp = ndp

    res = 0
    for i in range(n + 1):
        if 2 * i > n:
            res += dp[i]
    print(res)
resolve()

Submission status: Accepted

Solution code:
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(N+1):
        if i < j:
            DP[i][j] = 0
        else:
            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:]))

Submission status: Accepted

Solution code:
N=int(input())
p=list(map(float,input().split()))
import numpy as np
d=np.zeros(N+2)
d[1]=1
for i in range(N):
    d[1:i+3]=(d[:i+2]*p[i]+d[1:i+3]*(1-p[i]))
print(sum(d[N//2+2:]))

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
LI = lambda : [float(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N = NI()
p = LI()
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):
        dp[i][j] = dp[i-1][j-1] * p[i-1] + dp[i-1][j] * (1-p[i-1])

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

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
LI = lambda : [float(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N = NI()
p = LI()
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] = dp[i-1][j-1] * p[i-1]
        dp[i][j] += dp[i-1][j] * (1-p[i-1])

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

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
LI = lambda : [float(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N = NI()
p = [0.0] + LI()
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] = dp[i-1][j-1] * p[i]
        dp[i][j] += dp[i-1][j] * (1-p[i])

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

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
LI = lambda : [float(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N = NI()
p = [0.0] + 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(0,i+1):
        if j > 0: dp[i][j] = dp[i-1][j-1] * p[i]
        dp[i][j] += dp[i-1][j] * (1-p[i])

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

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys, bisect, math, itertools
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

n = inp()
p = list(map(float, input().split()))
# dp[i][j]=最初のi枚のコインを投げた時に表がj枚になる確率
dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1

for i in range(n):
    for j in range(n):
        dp[i + 1][j + 1] += dp[i][j] * p[i]  # i+1枚目が表
        dp[i + 1][j] += dp[i][j] * (1.0 - p[i])  # i枚目が裏

print(sum([dp[n][i] for i in range(math.ceil(n / 2), n + 1)]))
# for i in dp:
#     print(i)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue May  5 00:32:28 2020

@author: Kanaru Sato
"""

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

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

for i in range(n,0,-1):
    index = i-1
    for j in range(n-i+2):
        if index == n-1 and j == 0:
            dp[index][j] = 1-p[n-1]
        elif index == n-1 and j == 1:
            dp[index][j] = p[n-1]
        elif j == 0:
            dp[index][j] = dp[index+1][j]*(1-p[index])
        elif 1 <= j and j <= n-i:
            dp[index][j] = dp[index+1][j]*(1-p[index]) + dp[index+1][j-1]*(p[index])
        else:
            dp[index][j] = dp[index+1][j-1]*(p[index])

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

print(ans)

Submission status: Accepted

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

# dp[i][j]: 最初のi枚を投げたときに表がj枚となる確率
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]) # 裏

res = 0
for j in range(n + 1):
	if n < 2 * j: # 表の枚数 > 裏の枚数
		res += dp[n][j]

print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#H,W=map(int,input().split())
N=int(input())
coin=list(map(float,input().split()))
p=10**9+7
ma=[]
dp=[[0]*(N+3) for i in range(N+3)]
dp[1][1]=coin[0]
dp[1][0]=1-coin[0]
for i in range(1,N):
     for j in range(0,N):
         if j==0:
             dp[i+1][0]=dp[i][0]*(1-coin[i])
         dp[i+1][j+1]=dp[i][j+1]*(1-coin[i])+dp[i][j]*coin[i]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from numpy import zeros

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

dp = zeros(N + 1)
dp[0] = 1.0

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

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

Submission status: Accepted

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

dp = [1] + [0] * N
for p in P:
    dp = [p * a + (1 - p) * b for a, b in zip([0] + dp, dp)]

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

Submission status: Accepted

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

dp = [1] + [0] * N
for i, p in enumerate(P, 1):
    dp = [p * a + (1 - p) * b for a, b in zip([0] + dp, dp)]

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

Submission status: Accepted

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

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

for i, p in enumerate(P, 1):
    dp = [p * a + (1 - p) * b for a, b in zip([0] + dp, dp)]

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

Submission status: Accepted

Solution code:
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,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):]))

Submission status: Accepted

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
P = np.array([np.float64(p) for p in readline().split()], dtype=np.float64)


def solve():
    dp = np.zeros(N + 1, dtype=np.float64)
    dp[0] = 1.0 - P[0]
    dp[1] = P[0]
    for i in range(1, N):
        p = P[i]
        q = np.zeros_like(dp)
        q[1:] = dp[:-1]
        dp = dp * (1.0 - p) + q * p
    return dp[N // 2 + 1 :].sum()


if __name__ == "__main__":
    print(solve())

Submission status: Accepted

Solution code:
import sys
import copy

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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


def solve():
    dp = [0.0] * (N + 1)
    dp[0] = 1.0 - P[0]
    dp[1] = P[0]
    for i in range(1, N):
        ndp = [0.0] * (N + 1)
        p = P[i]
        for j in range(i, -1, -1):
            ndp[j + 1] += dp[j] * p
            ndp[j] += dp[j] * (1 - p)
        dp = ndp
    return sum(dp[N // 2 + 1 :])


if __name__ == "__main__":
    print(solve())

Submission status: Accepted

Solution code:
n = int(input())
p = list(map(float, input().split()))
dp = [0]*(n+2)
dp[1] = 1
for i in p:
    newdp = dp[:]
    for j in range(n+1):
        newdp[j+1] = dp[j]*i + dp[j+1]*(1-i)
    dp = newdp

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    p = tuple(map(float, input().split()))

    dp = [0 for i in range(N+1)]
    # iまで見たときに表の枚数がj枚の確率

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

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

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


main()

Submission status: Accepted

Solution code:
from math import ceil
def main():
    N = int(input())
    P = list(map(float,input().split()))
    f = [[0]*(N + 1) for _ in range(N + 1)]
    f[0][0] = 1 - P[0]
    f[0][1] = P[0]
    for i in range(1,N):
        p = P[i]
        f[i][0] = f[i - 1][0]*(1 - p)
        for j in range(max(1,ceil((N + 1)/2) - N + i - 3),i + 2):
            f[i][j] += p*f[i - 1][j - 1] + (1 - p)*f[i - 1][j]
    print(sum(f[N - 1][N //2 + 1:]))
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

#output
#dp[i][j]をi番目まで選んだ時の表の枚数がj枚である確率とする。

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

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

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

Submission status: Accepted

Solution code:
import numpy as np

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

dp = np.zeros((N + 1, N + 1), dtype=float)
dp[0][0] = 1
for i in range(N):
    dp[i + 1][1:] += dp[i][:-1] * P[i]
    dp[i + 1][:-1] += dp[i][:-1] * (1 - P[i])
print(sum(dp[N][(N + 1) // 2:]))

Submission status: Accepted

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

Submission status: Accepted

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


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

Submission status: Accepted

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

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

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy


def prob(i, values):
    result = 1
    idx = 0
    for idx, v in enumerate(values):
        i, rest = divmod(i, 2)
        if rest == 1:
            result *= v
        else:
            result *= 1 - v
        idx += 1
    return result


def solve(values, nb):
    LOG.debug((values))
    dp = [[0] * (nb + 1) for _ in range(nb // 2 + 1)]
    dp[0][0] = 1
    for j in range(1, nb + 1):
        dp[0][j] = dp[0][j - 1] * (1 - values[j - 1])
    total = dp[0][-1]
    for i in range(1, nb // 2 + 1):
        for j in range(i, nb + 1):
            dp[i][j] = (
                dp[i - 1][j - 1] * values[j - 1] + (1 - values[j - 1]) * dp[i][j - 1]
            )
        total += dp[i][-1]
    # LOG.debug(("\n" + "\n".join(map(str, dp))))
    return 1 - total


def do_job():
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    N = int(input())
    values = list(map(float, input().split()))
    # values = []
    # for _ in range(N):
    #     values.append(input().split())
    result = solve(values, N)
    # 6 digits float precision {:.6f} (6 is the default value)
    print("{:.10g}".format(result))


def configure_log():
    "Configure the log output"
    log_formatter = logging.Formatter("L%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Submission status: Accepted

Solution code:
def main():
    from bisect import bisect_left as bl, bisect_right as br, insort
    import sys
    import heapq
    # from math import *
    from collections import defaultdict as dd, deque
    def data(): return input()
    def mdata(): return map(float, data().split())
    out = sys.stdout.write
    # sys.setrecursionlimit(100000)
    INF = int(1e9)
    mod = int(1e9) + 7

    n = int(data())
    P = list(mdata())
    dp = [0.0] * (n // 2 + 2)
    dp[1] = float(1)
    for i in range(n):
        p=P[i]
        for j in range(len(dp) - 1, 0, -1):
            dp[j] = dp[j - 1] * (1 - p) + dp[j] * (p)
    print(sum(dp))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
# from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline()
def mdata(): return map(float, data().split())
out = sys.stdout.write
# sys.setrecursionlimit(100000)
INF = int(1e9)
mod = int(1e9) + 7

n = int(data())
P = list(mdata())
dp = [0.0] * (n // 2 + 2)
dp[1] = float(1)
for i in range(n):
    p=P[i]
    for j in range(len(dp) - 1, 0, -1):
        dp[j] = dp[j - 1] * (1 - p) + dp[j] * (p)
print(sum(dp))

Submission status: Accepted

Solution code:
def main():
    from bisect import bisect_left as bl, bisect_right as br, insort
    import sys
    import heapq
    # from math import *
    from collections import defaultdict as dd, deque
    def data(): return sys.stdin.readline()
    def mdata(): return map(float, data().split())
    out = sys.stdout.write
    # sys.setrecursionlimit(100000)
    INF = int(1e9)
    mod = int(1e9) + 7

    n = int(data())
    P = list(mdata())
    dp = [0.0] * (n // 2 + 2)
    dp[1] = float(1)
    for i in range(n):
        p=P[i]
        for j in range(len(dp) - 1, 0, -1):
            dp[j] = dp[j - 1] * (1 - p) + dp[j] * (p)
    print(sum(dp))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
# from math import *
from collections import defaultdict as dd, deque
def data(): return input()
def mdata(): return map(float, data().split())
out = sys.stdout.write
# sys.setrecursionlimit(100000)
INF = int(1e9)
mod = int(1e9) + 7

n = int(data())
P = list(mdata())
dp = [0.0] * (n // 2 + 2)
dp[1] = float(1)
for i in range(n):
    p=P[i]
    for j in range(len(dp) - 1, 0, -1):
        dp[j] = dp[j - 1] * (1 - p) + dp[j] * (p)
print(sum(dp))

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read():
    N = int(input().strip())
    P = list(map(float, input().strip().split()))
    return N, P


def solve(N, P):
    # dp[i, j]: i枚目まで投げて、表がj枚出る確率
    # dp[i, j] = dp[i-1, j-1] * p[j] + dp[i, j-1] * (1-p[j])
    # 2000x(N//2)のテーブルを作るとTLEするので、圧縮して解く
    dp = [[0 for j in range(N+1)] for i in range(2)]
    dp[0][0] = 1
    for j in range(1, N+1):
        dp[0][j] = dp[0][j-1] * (1.0 - P[j-1])
    ans = dp[0][-1]
    for i in range(1, N//2+1):
        b = i % 2
        dp[b][i-1] = 0.0
        for j in range(i, N+1):
            dp[b][j] = dp[(b-1)%2][j-1] * P[j-1] + dp[b][j-1] * (1.0 - P[j-1])
        ans += dp[b][-1]
    return "{:.10f}".format(1.0 - ans)


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
p = list(map(float, readline().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])
print(sum(dp[-1][n // 2 + 1:]))

Submission status: Accepted

Solution code:
def solve():
    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(0,i+1):
            dp[i+1][j+1] += dp[i][j] * p[i]
            dp[i+1][j] += dp[i][j] * (1.0 -p[i])
    

    ans = 0
    for i in range(N+1):
        if i > (N-i):
            ans += dp[-1][i]
    
    print(ans)
            
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n=int(input())
p=list(map(float,input().split()))

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

Submission status: Accepted

Solution code:
import sys 
input = sys.stdin.readline

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

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    coins = list(map(float,input().split()))
    dp = [[0 for i in range(n+1)] for j in range(n+1)]

    dp[0][0] = 1
        
    for pos in range(1,n+1):
        for heads in range(pos+1):
            if heads == 0:
                dp[pos][heads] = dp[pos-1][heads]*(1-coins[pos-1])
            else:
                dp[pos][heads] = dp[pos-1][heads]*(1-coins[pos-1])
                dp[pos][heads] += dp[pos-1][heads-1]*coins[pos-1]

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

main()

Submission status: Accepted

Solution code:
n=int(input())
p=list(map(float,input().split()))
# 最初の ii 枚のコインを投げたときに、表が jj 枚となる確率
dp=[[0.0]*(n+1) for i in range(n+1)]
dp[0][0]=1.0
for i in range(n):
  for j in range(n):
    dp[i+1][j+1]+=dp[i][j]*p[i]
    dp[i+1][j]+=dp[i][j]*(1-p[i])
    
ans=0.0
for i in range((n+1)//2,n+1):
  ans+=dp[n][i]
print(ans)

Submission status: Accepted

Solution code:
def list2d(a, b, c): return [[c] * b for i in range(a)]
mod =10**9+7

n = int(input())
p = list(map(float, input().split()))
dp = list2d(n + 1,n + 1 ,0)

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

Submission status: Accepted

Solution code:
n = int(input())
p = list(map(float, input().split()))
dp = [[0] * (2*n + 2) for i in range(n//2+1)]
dp[0][n+1] = p[0]
dp[0][n] = 1-p[0]
for i in range(n//2):
  p1, p2 = p[2*i+1], p[2*i+2]
  h,t = p1*p2,(1-p1) * (1-p2)
  m = 1 - h - t
  for j in range(n-i,n+i+2):
    plus = dp[i][j]
    dp[i+1][j+1] += plus * h
    dp[i+1][j] += plus * m
    dp[i+1][j-1] += plus * t
print(sum(dp[n//2][n+1:]))