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 sys

sys.setrecursionlimit(10 ** 9)


# map(int, sys.stdin.read().split())


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


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

    dp = [[0 for _ in range(N+1)] for i in range(N+1)]   #i枚投げたときの　j表が出た枚　のdpが確立
    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]

    n = (N+1)//2

    print(sum(dp[N][n:]))
    pass

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
from collections import deque
from fractions import Fraction as f
from copy import *
from bisect import *	
from heapq import *
from math import *
from itertools import permutations 
 
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
 
#sys.setrecursionlimit(10**6)
if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
def li():
	return [int(x) for x in input().split()]
def fli():
	return [float(x) for x in input().split()]	
def gi():	
	return [x for x in input().split()]
def fi():
	return int(input())
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())	
def gh():
	sys.stdout.flush()
def graph(n,m):
	for i in range(m):
		x,y=mi()
		a[x].append(y)
		a[y].append(x)
def bo(i):
	return ord(i)-ord('a')
		


tt=1



while tt>0:
	tt-=1
	n=fi()
	a=fli()
	dp=[[0 for i in range(n+1)] for j in range(n+1)]
	for i in range(n):
		if i==0:
			dp[i][0]=1-a[i]
			dp[i][1]=a[i]
		else:
			for j in range(0,n+1):
				dp[i][j]=dp[i-1][j]*(1-a[i])+(dp[i-1][j-1]*a[i] if j>0 else 0)
	ans=0			
	for i in range(n+1):
		if i>n-i:
			ans+=dp[n-1][i]
	print(ans)

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

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

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

print(sum_)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin


def ni(): return int(ns())


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


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N = ni()

p_array = list(map(float, stdin.readline().split()))

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

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


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

Submission status: Accepted

Solution code:
import sys
def main():
    N=int(sys.stdin.readline())
    p=[float(x) for x in sys.stdin.readline().split()]
    dp=[0 for _ in range(N+1)]
    dp[0]=1.0
    for i in range(1,N+1):
        for j in range(i,0,-1):dp[j]=dp[j-1]*p[i-1]+dp[j]*(1-p[i-1])
        dp[0]=dp[0]*(1-p[i-1])
    print(sum(dp[N//2+1:]))
if __name__=='__main__':main()

Submission status: Accepted

Solution code:
import sys
def main():
    N=int(sys.stdin.readline())
    p=[float(x) for x in sys.stdin.readline().split()]
    dp=[[0 for _ in range(N+1)] for _ in range(N+1)]
    dp[0][0]=1.0
    for i in range(1,N+1):
        dp[i][0]=dp[i-1][0]*(1-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:]))
if __name__=='__main__':main()

Submission status: Accepted

Solution code:
import sys
def main():
    N=int(sys.stdin.readline())
    p=[float(x) for x in sys.stdin.readline().split()]
    dp=[[0 for _ in range(N+1)] for _ in range(N+1)]
    dp[0][0]=1.0
    for i in range(1,N+1):
        dp[i][0]=dp[i-1][0]*(1-p[i-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:]))
if __name__=='__main__':main()

Submission status: Accepted

Solution code:
N = int(input())
p = list(map(float, input().split()))
dp = [[0.0 for i in range(N+1)] for _ in range(N+1)]
dp[0][0] = 1.0
for i in range(N):
    for j in range(i+1):
        # 表が出る
        dp[i+1][j+1] += dp[i][j] * p[i]
        # 裏が出る
        dp[i+1][j] += dp[i][j] * (1 - p[i])
temp = (N+1)//2
print(sum(dp[-1][temp:]))

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

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
p = [float(i) for i in 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):
        if not j:
            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+1)//2):]))

Submission status: Accepted

Solution code:
n = int(input())

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

dp = []

for i in range(n+1):
    temp = []
    for j in range(n+1):
        temp.append(0.0)
    
    dp.append(temp)

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


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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

dp = np.zeros(n + 1, float)
dp[0] = 1
for e in p:
    dp[1:] += dp[:-1] * e / (1 - e)
    dp *= 1 - e

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

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



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][j] for j in range(n//2+1, n+1)))

Submission status: Accepted

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

import numpy as np
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] *= (1-p[i])

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

Submission status: Accepted

Solution code:
#!python3

import numpy as np

LI = lambda: list(map(float, input().split()))

# input
N = int(input())
P = LI()


def main():
    dp = np.zeros((N + 1, N + 1))
    dp[0][0] = 1
    for i in range(1, N + 1):
        p = P[i - 1]
        bac = dp[i - 1][:i] * (1 - p)
        hos = dp[i - 1][:i] * p
        dp[i][:i] += bac
        dp[i][1 : i + 1] += hos
    ans = sum(dp[N][(N + 1) // 2:])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys;
import math;
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def get_array(): return list(map(float, sys.stdin.readline().strip().split()))
def get_string(): return sys.stdin.readline().strip()

n = int(input());
arr = get_array();
dp = [[0 for i in range(n+1)] for i in range(n+1)];
dp[0][0]=1;
for i in range(1,n+1):
    dp[i][0]=dp[i-1][0]*(1-arr[i-1])
for i in range(1,n+1):
    for j in range(1,n+1):
        if(i==j):
            dp[i][j]=dp[i-1][j-1]*arr[i-1];
            continue
        if(j>i):
            continue;
        dp[i][j] = dp[i-1][j-1]*arr[i-1]+dp[i-1][j]*(1-arr[i-1]);
#print(dp);
ans = 0;
for i in range(n+1):
    if(i>=n//2 + 1):
        ans += dp[n][i];
print(ans);

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
arr = 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(i + 1):
        dp[i + 1][j + 1] += dp[i][j] * arr[i]
        dp[i + 1][j] += dp[i][j] * (1 - arr[i])

dp = dp[-1]

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

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    Ps = list(map(float, input().split()))

    Qs = [1-P for P in Ps]

    dp = [0.0] * (N+2)
    dp[0] = 1.0
    for i, (P, Q) in enumerate(zip(Ps, Qs)):
        dp2 = [0.0] * (N+2)
        for j in range(i+1):
            dp2[j] += dp[j] * Q
            dp2[j+1] += dp[j] * P
        dp = dp2

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


solve()

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    Ps = list(map(float, input().split()))

    Qs = [1-P for P in Ps]

    dp = [0.0] * (N+2)
    dp[0] = 1.0
    for P, Q in zip(Ps, Qs):
        dp2 = [0.0] * (N+2)
        for j in range(N+1):
            if dp[j] == 0.0: continue
            dp2[j] += dp[j] * Q
            dp2[j+1] += dp[j] * P
        dp = dp2

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


solve()

Submission status: Accepted

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

dp=[]
for i in range(n+1):
    dp.append([0]*(n+1))
dp[1][0]=(1-arr[0])
dp[1][1]=arr[0]

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

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

res = 0.0
for i in range(N//2+1, N+1):
    res += dp[N][i]
print("{:.10f}".format(res))

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

    dp = [0.0]*(N//2+2)
    dp[0] = 1.0
    for i in range(N):
        dp_ = [0.0]*(N+1)
        dp_[N//2+1]=dp[N//2+1]
        for j in range(min(i+1,N//2+1),-1,-1):
            dp_[j]+=dp[j-1]*P[i]
            dp_[j-1]+=dp[j-1]*(1-P[i])
        dp=dp_.copy()
    print(dp[N//2+1])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

dp=[[0]*(n+1) for _ in range(n+1)]
dp[0][0]=1
for k in range(1,n+1):
    dp[0][k]=0
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])

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

Submission status: Accepted

Solution code:
n = int(input())
prob = 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] = dp[i-1][j] * (1.0 - prob[i-1])
        else:
            dp[i][j] = prob[i-1] * dp[i-1][j-1] + (1.0 - prob[i-1]) * dp[i-1][j]

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

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=float)
dp[0,0] = 1

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

Submission status: Accepted

Solution code:
n = int(input())
p = [float(i) for i in input().split()]
#i枚目までのコインでj枚表が出ている確率
dp = [[0] * i for i in range(2,n+2)]

dp[0][1] = p[0]
dp[0][0] = 1-p[0]
ans = 0
if n != 1:
    for i in range(1,n):
        for j in range(len(dp[i])-1):
            #i枚目で裏が出る確率
            dp[i][j] += dp[i-1][j] * (1-p[i])
            #i枚目で表が出る確率
            dp[i][j+1] += dp[i-1][j] * p[i]
    for i in range(1,(n+1)//2+1):
        ans += dp[n-1][-i]
    print(ans)
else:
    print(p[0])

Submission status: Accepted

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

# i-1 まで見たときに表が 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):
        dp[i][j] += (1-p[i-1])*dp[i-1][j]
        if j >= 1:
            dp[i][j] += p[i-1]*dp[i-1][j-1]

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

Submission status: Accepted

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

# i-1 まで見たときに表が 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):
        dp[i][j] += (1-p[i-1])*dp[i-1][j]
        if j >= 1:
            dp[i][j] += p[i-1]*dp[i-1][j-1]

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

Submission status: Accepted

Solution code:
def main():
    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(i + 1):
            dp[i][j] = dp[i - 1][j] * (1 - P[i]) + dp[i - 1][j - 1] * P[i]
    print(sum(dp[n][n // 2 + 1:]))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

N = int(input())
M = N // 2 + 1
P = np.array(input().split(),dtype = float)

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

for i in range(N):
  tmp = dp[i].copy()
  dp[i + 1] = tmp * (1 - P[i])
  tmp = np.roll(tmp,1)
  dp[i + 1] += tmp * P[i] 
  
print(sum(dp[-1][M:]))

Submission status: Accepted

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

N = int(buf.readline())
M = N // 2 + 1
P = np.array(buf.readline().split(),dtype = float)

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

for i in range(N):
  tmp = dp[i].copy()
  dp[i + 1] = tmp * (1 - P[i])
  tmp = np.roll(tmp,1)
  dp[i + 1] += tmp * P[i] 
  
print(sum(dp[-1][M:]))

Submission status: Accepted

Solution code:
N = int(input())
P = list(map(float, input().split()))
dp = [[0]*(N+1) for _ in range(N)]
dp[0][0] = 1-P[0]
dp[0][1] = P[0]
for i in range(N):
    for k in range(N+1):
        if i-1 >= 0:
            dp[i][k] += dp[i-1][k]*(1-P[i])
            if k-1 >= 0:
                dp[i][k] += dp[i-1][k-1]*P[i]
ans = 0
for i in range(N+1):
    if i >= (-(-N//2)):
        ans += dp[-1][i]
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    assert N % 2 == 1
    M = (N + 1) // 2
    P = list(map(float, input().split(' ')))
    dp = [[0 for _ in range(M + 1)] for _ in range(N)]
    dp[0][0] = 1 - P[0]
    dp[0][1] = P[0]
    for n in range(1, N):
        p = P[n]
        for m in range(min([n + 1, M]) + 1):
            if 1 <= m < M:
                dp[n][m] = dp[n - 1][m] * (1 - p) + dp[n - 1][m - 1] * p
            elif m == M:
                dp[n][m] = dp[n - 1][m] + dp[n - 1][m - 1] * p
            else:
                # m == 0
                dp[n][m] = dp[n - 1][m] * (1 - p)
    print(dp[-1][-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
li=[float(k) for k in input().split()]
dp=[[0 for i in range(len(li)+1)] for j in range(len(li)+1)] 
x=len(li)
dp[0][0]=1
for a in range(1,x+1):
  ph=li[a-1]
  pt=1-li[a-1]
  dp[a][0]=pt*dp[a-1][0]
  
  for b in range(1,a+1):
    dp[a][b]=dp[a-1][b-1]*ph+pt*dp[a-1][b]
ans=0
for i in range(x//2+1,x+1):
  ans=ans+dp[x][i]
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=input().split()
li=[float(i) for i in l]
#dp[i][j] denotes out of first i tosses get j heads
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):
	dp[i][0]=dp[i-1][0]*(1-li[i-1])
for j in range(1,n+1):
	dp[0][j]=0
for i in range(1,n+1):
	for j in range(1,i+1):
		dp[i][j]=(dp[i-1][j-1]*li[i-1])+dp[i-1][j]*(1-li[i-1])
prob=0
for j in range(n+1):
	if(j>n/2):
		prob+=dp[n][j]
print(prob)

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def read_floats():
    return list(map(float, input().strip().split(' ')))


def solve():
    """
    OPT[N][M] - from N coins having exactly M head
    OPT[N][M] = OPT[N-1][M]*(1-P[N])+OPT[N-1][M-1]*P[N]

    OPT[0][0] = 1
    OPT[i][0] = P[i]
    """
    N = read_int()
    P = read_floats()
    OPT = [
        [0]*(N+1) for _ in range(N+1)
    ]
    OPT[0][0] = 1
    for i in range(1, N+1):
        for j in range(N+1):
            OPT[i][j] = OPT[i-1][j]*(1-P[i-1])
            if j > 0:
                OPT[i][j] += OPT[i-1][j-1]*P[i-1]
    return sum(OPT[-1][(N+1)//2:])


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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

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

    print(res)


if __name__ == '__main__':
    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[i+1][j]:i枚目のコインまで見たときに表がj枚でている確率
dp[0][0] = 1.0

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

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
#for _ in range(int(input())):
n=int(input())
#	n,m=map(int,input().split())
#	s=input().strip()
p=list(map(float,(input().split())))
dp=[[0]*(n+1) for i in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
	for j in range(n+1):
		if j==0:dp[i][j]=(1-p[i-1])*dp[i-1][j]
		else:dp[i][j]=p[i-1]*dp[i-1][j-1]+(1-p[i-1])*dp[i-1][j]
ans=0
for i in range(n//2+1,n+1):
	ans+=dp[n][i]
print(ans)

Submission status: Accepted

Solution code:
# python3だとTLE,pypy3だとAC

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    p = list(map(float, input().split()))
    dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
    p_mul = 1
    dp[0][0] = 1
    for i in range(1, N + 1):
        p_mul *= (1-p[i-1])
        dp[i][0] = p_mul
    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:]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter
from collections import deque
import math
import bisect
import sys
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

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

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

        else:
            #裏の時、表が出た枚数jはかわらない+確率は1-p[i]
            dp[i][j] += dp[i - 1][j] * (1 - p[i])
            if dp[i - 1][j] == 0:continue
            #表の時、表が出た数は+1、確率はp[i]
            dp[i][j + 1] += dp[i - 1][j] * p[i]
print(sum(dp[-1][n//2 + 1:]))

Submission status: Accepted

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N = I()
P = list(map(float,input().split()))
dp = FILL2(0,N+3,N+3)
dp[0][0] = 1
for i in range(N):
    for j in range(N):
        dp[i+1][j+1] += dp[i][j]*P[i]
        dp[i+1][j] += dp[i][j]*(1-P[i])
print(sum(dp[N][N//2+1:]))

Submission status: Accepted

Solution code:
N=int(input())
P= list(map(float,input().split()))
ans=[[0 for e in range(2*N+3)] for f in range(N+1)]
ans[0][N+1]=1
for n in range(1,N+1):
 for i in range(N+1-n,N+2+n):
  ans[n][i]=ans[n-1][i-1]*P[n-1]+ans[n-1][i+1]*(1-P[n-1])
t=0
for i in range(N+1,2*N+3):
 t+=ans[N][i]
print(t)

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

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

Submission status: Accepted

Solution code:
from sys import stdin, stdout
from collections import deque, defaultdict
import math as m

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	n = int(rl())
	P = [0]
	P.extend(list(rlf()))

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

	for r in range(1, n + 1): 
		for c in range(r, n + 1): 
			dp[r][c] = P[c]*dp[r-1][c-1] + (1- P[c])*dp[r][c-1]

	ans = sum(dp[i][n] for i in range(m.ceil(n/2), n + 1))
	print(ans)
	
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

dp=[defaultdict(float) for i in range(n)]

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

Submission status: Accepted

Solution code:
n=int(input())
import math
p=list(map(float,input().split()))
for i in range(n):
    p[i]=p[i]*100
dp=[[0]*(n) for i in range(n+1)]
dp[0][0]=(100-p[0])/100
for i in range(1,n):
    dp[0][i]=dp[0][i-1]*(100-p[i])/100
# print(dp[0][1],1-p[2],dp[0][1]*(1-p[2]))
for i in range(1,n+1):
    for j in range(i-1,n):
        if j==0:
            temp1=1 
            temp2=0 
        else:
            temp1=dp[i-1][j-1]
            temp2=dp[i][j-1]
        dp[i][j]=temp1*p[j]/100+temp2*(100-p[j])/100
        dp[i][j]=dp[i][j]
ans=0
# print(dp)
for i in range(n//2+1,n+1):
    ans+=dp[i][n-1]
print(ans)

Submission status: Accepted

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

dp=[[1.0]*(n+1) for i 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):
    dp[i][0]=dp[i-1][0]*(1.0-h[i-1])

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

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from collections import defaultdict as dd    
n=int(input())
l=list(map(float,input().split()))
dp=[[0]*(n+1) for i in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
    for j in range(n+1):
        if(j==0):
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])
        else:
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])+dp[i-1][j-1]*l[i-1]
ans=0
for i in range(n//2+1,n+1):
    ans+=dp[n][i]
print(ans)

Submission status: Accepted

Solution code:
#I
N=int(input())
P=[0]+[float(x) for x in input().split()]

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

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

Submission status: Accepted

Solution code:
import numpy as np

if __name__=='__main__':
    N = int(input())
    p = np.array(list(map(float,input().split())))
    
    dp = np.zeros([N+1,N+1],dtype=float)
    dp[0][0] = 1.0
    
    for i,p in enumerate(p):
        dp[i+1][:] = dp[i][:]*(1-p)
        dp[i+1][1:] += dp[i][:-1]*p
    
    
    ans = N//2 + 1
    print(dp[N][ans:].sum())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    N = int(input())
    probability = list(map(float, input().rstrip().split()))

    # dp[i][j] = i枚目までで表がj枚出る確率
    dp = [[0] * (N+1) for _ in range(N+1)]
    dp[0][0] = 1

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin, stdout


def solve():
    n = int(input())
    A = [float(i) for i in stdin.readline().split()]
    dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(1, n+1):
        for j in range(0, i+1):
            if j == 0: dp[i][j] = (1 - A[i-1]) * dp[i-1][j]
            else: dp[i][j] = (A[i-1] * dp[i-1][j-1]) + ((1 - A[i-1]) * dp[i-1][j])
    ans = 0
    for i in range((n+1)//2, n+1):
        ans += dp[-1][i]
    return ans

print(solve())