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:

import math
from pprint import pprint


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

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

    print(ans)

submit()

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

Submission status: Accepted

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)
def input():
    return sys.stdin.readline()[:-1]

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

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

for c in P:
#    prev = dp.copy()
    dp = np.append(dp[:-1] * (1-c), 0) + np.append(0, dp[:-1] * c)
#    print(dp)

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

Submission status: Accepted

Solution code:
n=int(input())

l=list(map(float,input().split()))
k=[0]*(n+1)
k[0]=1
for p in l:
    for j in range(n,-1,-1):
        k[j]*=(1-p)
        if j!=0:k[j]+=k[j-1]*p

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

Submission status: Accepted

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]

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

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

for c in P:
#    prev = dp.copy()
    dp = np.append(dp[:-1] * (1-c), 0) + np.append(0, dp[:-1] * c)
#    print(dp)

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

Submission status: Accepted

Solution code:
N = int(input())
P = list(map(float, input().split()))
dp = [[0] * 3010 for _ in range(3010)]
dp[0][0] = 1
# dp[i][j] iまでのコインを使って、j枚の表が出る確率
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[N][N//2+1:]))

Submission status: Accepted

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

dp = [[0] * 3010 for _ in range(3010)]
dp[0][1] = 1
dp[0][0] = 1
# dp[i][j] iまでのコインを使って、j枚の表が出る確率
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[N][N//2+1:]))

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

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

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

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(float, input().split()))
ans = 0
if n == 1:
    ans = a[0]
else:
    dp = [[0]*(n//2+1) for _ in range(n)]
    dp[0][0] = a[0]
    dp[0][1] = 1-a[0]

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

Submission status: Accepted

Solution code:
N = int(input())
P = [float(v) for v in input().split()]
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]

#  for i,p in enumerate(P,1): dp[i][0] = (1-p)
dp[0][0] = 1
dp[1][0] = P[0]

threshold = N // 2

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

ans = 0

for i,v in enumerate(dp[N]):
    if i > threshold:
        ans += v
print(ans)

Submission status: Accepted

Solution code:
#string = ' '.join(list(input() for _ in range(int(input()))))
n = int(input())
a = 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(n+1):
        if j==0:
            dp[i][j] = (1-a[i-1])*(dp[i-1][j])
        else:
            dp[i][j] = (a[i-1]*dp[i-1][j-1])+((1.0-a[i-1])*dp[i-1][j])
ans = 0.0
for i in range((n//2)+1,n+1):
    ans+=dp[n][i]
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(float, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

N = ii()
P = li()

dp = dp2(0, N+1, N)
dp[0][0] = 1 - P[0]
dp[0][1] = P[0]

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
n = int(input())#奇数
p = [0] + list(map(float,input().split()))
ans = 0
#dp[i][j] = i番目までのコインで表がj枚になる確率
'''dp[i][j] = dp[i-1][j-1]*p[i] + dp[i-1][j]*(1-p[i])
ans = dp[n][n//2+1]+...+dp[n][n]
'''
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])
for i in range(1,n+1):
  for j in range(1,i+1):
    dp[i][j] = dp[i-1][j-1]*p[i] + dp[i-1][j]*(1-p[i])
for j in range(n//2+1,n+1):
  ans += dp[n][j]
print(ans)

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(0, 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] + dp[i-1][j] * (1 - P[i-1])
# print(*dp, sep='\n')
print(sum(dp[N][N//2+1:]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# I-Coin

'''
5
0.42 0.01 0.42 0.99 0.42
'''


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

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

# i=0: 0枚中j(>0)枚が表の確率 = 0
dp[0][0] = 1

# j=0: i(>0)枚中0枚が表の確率 = 全て裏の確率
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(dp)
print(sum(dp[N][int((N+1)/2):]))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n=int(input())
p=list(map(float,input().split()))
#dp[i][j] i tells u i coins from 0, j tells u j heads 
#dp[n+1][n+1]
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):
#     dp[0][i]=0.0
for i in range(1,n+1):
    for j in range(0,n+1):
        if(j==0):
            dp[i][j]=(1.0-p[i-1])*dp[i-1][j]
        else:
            dp[i][j]=p[i-1]*dp[i-1][j-1]+(1.0-p[i-1])*dp[i-1][j]

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

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

ans = 0

for i in range(N+1):
    if N-i<i:
        ans += DP[N][i]

print(ans)

Submission status: Accepted

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

#dp[i][j]:=i枚コインの中から、j個表が出る確率
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+1)//2:]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
import numpy as np

def main():
    N = int(input())
    a = list(map(float,input().split()))
    ha = -(-N//2)
    
    dp = np.zeros(N+1,dtype=float)
    dp[0] = 1
    for num in a:
        front = np.zeros(N+1,dtype=float)
        front[1:] = dp[:-1]*num
        dp *= (1-num)
        dp += front
    
    print(np.sum(dp[ha:]))
    
if __name__ == "__main__":
    main()

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

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][j]
        else:
            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+1):
    if j > (N-j):
        ans += dp[N][j]
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

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

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())

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

for p in map(float, input().split()):
  tmp = (1. - p) * dp
  tmp[1:] += p * dp[:-1]
  dp = tmp

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

Submission status: Accepted

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

print(sum([dp[N][j] for j in range(N+1) if j >= -(-N//2)]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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 + 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]
res = 0
for j in range(N // 2 + 1, N + 1): res += dp[-1][j]
print(res)

Submission status: Accepted

Solution code:
from decimal import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]

n = val()
l = li4()
mihe = n//2 + 1


curr = 1
for i in l:curr *= (1 - i)
dp = [0 for i in range(n + 1)]
dp[0] = 1

for i in range(n):

    for j in range(i + 1,-1,-1):
        if not j:dp[j] *= 1 - l[i]
        else:dp[j] = dp[j-1] * l[i] + dp[j] *(1 - l[i])

ans = 0
for i in dp[-mihe:]:
    ans += i

print(round(ans,10))

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

print(ans)

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][1] = P[0]
dp[0][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:]))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n=int(input())
A=list(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):
    for j in range(n+1):
        if i==0:
            if j>i:
                dp[i][j]=0
            else:
                dp[i][j]=1
        elif j==0:
            if i>1:
                dp[i][j]=dp[i-1][j]*(1-A[i-1])
            else:
                dp[i][j]=1-A[i-1]
        if i!=0 and j!=0:
            dp[i][j]=dp[i-1][j-1]*A[i-1]+dp[i-1][j]*(1-A[i-1])
sum=0
for s in range(n//2+1,n+1):
        sum+=dp[-1][s]
print(sum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
inp = list(map(lambda x: float(x), 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] += dp[i][j]*(1-inp[i])
        dp[i+1][j+1] += dp[i][j]*inp[i]

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

Submission status: Accepted

Solution code:
import random

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

# dp[i][j] = i番目までのコインを振ったとき、表の数がj枚となる確率
dp = [[0.0]*(n+1) for _ in range(n+1)]
dp[0][0] = 1.0

for i in range(n):
    for j in range(n):
        # 表のとき
        dp[i+1][j+1] += dp[i][j] * p[i]
        # 裏のとき
        dp[i+1][j] += dp[i][j] * (1 - p[i])

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np

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

dp = [np.zeros(n + 1) for _ in range(n)]

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

l = dp[-1]

print(l[len(l)//2:].sum())

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

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

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

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

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
p = list(map(float, input().split()))
index = n//2 + 1

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

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

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

Submission status: Accepted

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

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

for i in range(n):
    for j in range(n+1):

        if i==0:
            dp[0][0]=1-p[i]
            dp[0][1]=p[i]
        else:
            #表が出る
            if dp[i-1][j-1]!=0:
                dp[i][j]+=dp[i-1][j-1]*p[i]
            #裏
                dp[i][j-1]+=dp[i-1][j-1]*(1-p[i])

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

Submission status: Accepted

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

#dp[n][n]=0

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

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

print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

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

#dp[n][n]

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

Submission status: Accepted

Solution code:
N = int(input())
p = list(map(float, input().split()))
dp = [0] * (N+1) # the probability of getting j heads
dp[0] = 1
for i in range(N):
    ndp = [0] * (N+1)
    ndp[0] = dp[0] * (1 - p[i])
    for j in range(1, N+1):
        ndp[j] = dp[j-1] * p[i] + dp[j] * (1 - p[i])
    dp = ndp
print(sum(dp[N//2+1:]))

Submission status: Accepted

Solution code:
# dp[i][j]：i枚で表がj枚になる確率
# 1 - sum(:dp[N][(N+1)//2])を求めればいいため，dp[N][(N+1)//2:]は求める必要が無い
# jが大きい順に更新すればdp[i][j]のjを保持する必要はない

N = int(input())
P = list(map(float, input().split()))
overhalf_N = (N+1)//2
underhalf_N = overhalf_N - 1

dp = [0]*(N+1) # dp[N][j]：N枚で表がj枚になる確率

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

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

print(1-sum(dp[:overhalf_N]))

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(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]
    
print(sum(dp[-1][(n+1)//2:]))

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[1][0] = 1 - P[0]
dp[1][1] = P[0]

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

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

Submission status: Accepted

Solution code:
#コインで裏をn回出す確率

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

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

    #dp[j]:裏がj枚でる確率
    dp = [1] + [0]*(N//2)
    for i in range(N):
        for j in range(i+1, -1, -1):
            if j==0:
                dp[j] = dp[j]*p[i]
            elif j<=(N//2):
                dp[j] = dp[j-1]*(1-p[i]) + dp[j] * p[i]
    res = sum(dp)
    print('{:.9f}'.format(res))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007
    N = int(input())
    p = list(map(float, input().split()))
    #dp[j]:裏がj枚でる確率
    dp = [1] + [0]*(N//2)
    for i in range(N):
        for j in range(i+1, -1, -1):
            if j==0:
                dp[j] = dp[j]*p[i]
            elif j<=(N//2):
                dp[j] = dp[j-1]*(1-p[i]) + dp[j] * p[i]

    res = sum(dp)
    print('{:.9f}'.format(res))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007
    N = int(input())
    p = list(map(float, input().split()))
    #dp[j]:裏がj枚でる確率
    dp = [1] + [0]*(N//2)
    for i in range(N):
        for j in range(i+1, -1, -1):
            if j==0:
                dp[j] = dp[j]*p[i]
            elif j<=(N//2):
                dp[j] = dp[j-1]*(1-p[i]) + dp[j] * p[i]

    res = sum(dp)
    print('{:.9f}'.format(res))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
P = list(map(float, input().split()))
import numpy as np
def prob_ret():
  prob = [0.0]*(N+1)
  prob[0] = 1
  prob=np.array(prob)
  for n in range(N):
    p = prob[:N]*P[n]
    prob = prob * (1-P[n])
    prob[1:] = prob[1:] + p
  return sum(prob[N//2+1:])
print(prob_ret())

Submission status: Accepted

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

# dp = [[None] * 1501 for i in range(3000)]
# def dfs(i=0, at=(n + 1) // 2):
#     if i == n:
#         return int(at <= 0)
#     at = max(at, 0)
#     if dp[i][at] is not None:
#         return dp[i][at]
#
#     r = dfs(i + 1, at - 1) * a[i] + dfs(i + 1, at) * (1 - a[i])
#     dp[i][at] = r
#     return r
# print(dfs())

dp = [[0] * 1501 for i in range(3000)]
dp[n][0] = 1
for i in reversed(range(n)):
    for at in reversed(range((n + 1) // 2 + 1)):
        r = dp[i + 1][max(0, at - 1)] * a[i] + dp[i + 1][at] * (1 - a[i])
        dp[i][at] = r

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

Submission status: Accepted

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

mid=(n+2)//2
dp=[[0]*(n+1) for i 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+1):
        if dp[i][j]!=0:
            #表が出るとき
            dp[i+1][j+1]+=dp[i][j]*p[i+1]
            #裏
            dp[i+1][j]+=dp[i][j]*(1-p[i+1])
print(sum(dp[-1][mid:]))

Submission status: Accepted

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

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

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

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

print(ans)

Submission status: Accepted

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

l = [1]

for i in range(n):
    t1 = [j*(1-p[i]) for j in l]
    t1.append(0)
    t2 = [0]+[j*p[i] for j in l]
    l = [t1[j] + t2[j] for j in range(len(t1))]

l.reverse()
print(sum([l[i] for i in range((n+1)//2)]))

Submission status: Accepted

Solution code:
import numpy as np

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

dp = np.zeros(N + 2)
dp[1] = 1

for p in P:
    q = 1 - p
    dp[1:] = dp[:N + 1] * p + dp[1:] * q

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

Submission status: Accepted

Solution code:

N = int(input())

fac = [1]
for i in range(N):
    i += 1
    fac.append(fac[-1] * i)

def nCr(n,r):
    return fac[n] // (fac[r] * fac(n-r))

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

"""

dpだよな
表と裏がa,N-a枚となる確率は？
無理かなぁ

左から見ていってdp?
表がa枚になる確率は p*(a-1枚の確率) + (1-p)*(a枚の確率)
→いけそう

"""

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

for loop in range(N):

    ndp = [0] * (N+1)

    for i in range(N):

        ndp[i+1] += dp[i] * p[loop]
        ndp[i] += dp[i] * (1-p[loop])

    dp = ndp

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

print (ans)

Submission status: Accepted

Solution code:
import collections
N = int(input())
A = list(map(float,input().split()))
K = N//2  + 1
dp = [[0 for _ in range(N + 1) ] for _ in range(N + 1)]
if N == 0: 
    print(0)
    exit
dp[0][0] = 1
ans = 0
for i in range(1,N+1):
    for j in range(i+1):
        if j - 1 < 0:
            dp[i][j] = dp[i-1][j]*(1-A[i-1])
        else:
            dp[i][j] = dp[i-1][j-1]*A[i-1] + dp[i-1][j]*(1-A[i-1])
for i in range(K,len(dp[N])):
        ans+=dp[N][i]
print(ans)