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

print(sum(dp[N][i] for i in range(N+1) if 2*i>=N))

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

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

Submission status: Accepted

Solution code:
N=int(raw_input())
P=[float(x) for x in raw_input().split()]
A=[[0 for i in range(N+1)] for j in range(N+1)]
A[1][0]=1-P[0]
A[1][1]=P[0]
for j in range(2,N+1):
    A[j][0]=A[j-1][0]*(1-P[j-1])
    for k in range(1,j+1):
        A[j][k]=A[j-1][k]*(1-P[j-1]) + A[j-1][k-1]*(P[j-1])
print(sum(A[N][N/2+1:]))

Submission status: Accepted

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

Submission status: Accepted

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

# dp[i][h]: i回投げてh回表がでる確率
dp = [[0]*(N+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(1, N+1):
    for h in range(i+1):
        if h-1<0:
            dp[i][h] = dp[i-1][h]*(1-p[i-1])
        else:
            dp[i][h] = dp[i-1][h-1]*p[i-1] + dp[i-1][h]*(1-p[i-1])
    # print(dp)
print(sum(dp[N][N//2+1:]))

Submission status: Accepted

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

Submission status: Accepted

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


N = int(fin())
p_list = [float(elem) for elem in fin().split()]


dp = [0] * (N + 1)
dp[0] = 1
for i, p in enumerate(p_list, start=1):
    next_dp = [0] * (N + 1)
    next_dp[0] = dp[0] * (1 - p)
    for j in range(1, i):
        next_dp[j] = dp[j - 1] * p + dp[j] * (1 - p)
    next_dp[i] = dp[i - 1] * p
    dp = next_dp


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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

#i枚中j枚が表
for i in range(1, N):
    for j in range(1, N+1):
        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, N+1):
    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 j in range(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])
        elif j==i+1:
            dp[i][j]=dp[i-1][j-1]*p[i]
        else:
            dp[i][j]=dp[i-1][j]*(1-p[i])+dp[i-1][j-1]*p[i]
ans=0
for j in range(N+1):
    if j>N-j:
        ans+=dp[N-1][j]
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
p = list(lf())

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

Submission status: Accepted

Solution code:
n = int(raw_input())
p = map(float, raw_input().split())
dp = [[0.00 for i in xrange(3001)] for _ in xrange(3001)]

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

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

res = 0.0
for i in xrange(n + 1):
    red = n - i
    if i > red:
        res += dp[n-1][i]
print res

Submission status: Accepted

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

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

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

Submission status: Accepted

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

dp = [[0]*(N+1) for i in range(N+1)]
for i in range(N+1):
    if N <= 2*i:
        dp[N][i] = 1.
for c in range(N-1, -1, -1):
    p = P[c]
    for k in range(N-1, -1, -1):
        dp[c][k] = r = p * dp[c+1][k+1] + (1.-p) * dp[c+1][k]
print("%.10f" % dp[0][0])

Submission status: Runtime Error

Solution code:

class Solution:
  def __init__(self):
    self.n=int(input())
    self.p=list(map(float, input().strip().split()))
    self.k=(self.n//2)+1
    self.ans=0
  def func(self,i,cp,count):
    if count>=self.k and i==self.n-1:      
      self.ans+=cp
    if i+1<self.n:
      self.func(i+1, cp*self.p[i+1], count+1)
      self.func(i+1, cp*(1-self.p[i+1]), count)
  def sol(self):
    self.func(-1,1,0)
    return self.ans
s=Solution()
print(s.sol())

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from decimal import Decimal
decimal.getcontext().prec = 10

from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

# ---------------------------------------

N = inp()
p = [0] + list(map(Decimal, 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(0, i+1):
        if j > 0:
            dp[i][j] = dp[i-1][j] * (1 - p[i]) + dp[i-1][j-1] * p[i]
        else:
            dp[i][j] = dp[i-1][j] * (1 - p[i])
_debug(dp)
ans = 0
for j in range(N//2 + 1, N + 1):
    ans += dp[N][j]
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
p = [0] + list(input().split())

for i in range(1, N+1):
    item = p[i].replace('0.', '')
    p[i] = int(item)

#print(p)

dp = np.zeros((3100, 3100))
#dp[i, j] = i枚目までのコインを投げて，表の個数がj枚である確率 * (10**(2*i))
#pythonのlistだと遅いので，numpyにおけるベクトル漸化式としてdpを埋めていく

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

for i in range(2, N + 1):
    dp[i] = (np.roll(dp[i-1], 1) * p[i] + dp[i-1] * (100-p[i])) // 10**max(0, i-10)
    #dp[i][j] = i-1枚目までで表がj-1かつi回目で表　＋　i-1回目までで表がj枚かつi回目で裏（MECE）
    #つまり，dp[i][j] = dp[i-1][j-1] * p[i] + dp[i-1][j] * (1 - p[i])
    #numpyを使ってベクトル漸化式と見ることで，for_loopを一層分解消。
    #print(i, j, dp[i][j])
    #プログラムの仕組み上，iが一つ進むと，100 * 100 = 10**4　ずつスケールが大きくなっていく。10**10で打ち切る。


ans = 0

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

dig = min(2*N, 10)

print(ans/10**dig)

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
p = [0] + list(input().split())

for i in range(1, N+1):
    item = p[i].replace('0.', '')
    p[i] = int(item)

#print(p)

dp = np.zeros((3100, 3100))
#dp[i, j] = i枚目までのコインを投げて，表の個数がj枚である確率 * (10**(2*i))
#pythonのlistだと遅いので，numpyにおけるベクトル漸化式としてdpを埋めていく

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

for i in range(2, N + 1):
    dp[i] = (np.roll(dp[i-1], 1) * p[i] + dp[i-1] * (100-p[i]))
    #dp[i][j] = i-1枚目までで表がj-1かつi回目で表　＋　i-1回目までで表がj枚かつi回目で裏（MECE）
    #つまり，dp[i][j] = dp[i-1][j-1] * p[i] + dp[i-1][j] * (1 - p[i])
    #numpyを使ってベクトル漸化式と見ることで，for_loopを一層分解消。
    #print(i, j, dp[i][j])
    #プログラムの仕組み上，iが一つ進むと，100 * 100 = 10**4　ずつスケールが大きくなっていく。


ans = 0

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

dig = min(2*N, 10)

print(ans/10**(2*N))

Submission status: Runtime Error

Solution code:
n= int(input())
p =[float(x) for x in range(int(input()))]
dp = [[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])
an=0
for i in range((n+1)//2,n+1):
    an+=dp[n][i]
print(an)

Submission status: Runtime Error

Solution code:
n= int(input())
p =[int(x) for x in range(int(input()))]
q= [1-int(x) for x in range(int(input()))]
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])
an=0
for i in range((n+1)//2,n+1):
    an+=dp[n][i]
print(an)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# from collections import deque
# from sys import setrecursionlimit

# setrecursionlimit(1000000)


# INF = float("inf")

# d = deque()
# ---Input---#
n = int(input())
# n, k = map(int, input().split())
p = list(map(float, input().split()))
p = [-1] + p

memo = [[-1 for _ in [0] * (n + 1)] for _ in [0] * (n + 1)]
memo[0][0] = 1
for i in range(len(p))[1:]:
    memo[0][i] = 0
    memo[i][0] = memo[i - 1][0] * (1 - p[i])
memo[0][0] = 1


def dp(i, j):
    if memo[i][j] == -1:
        memo[i][j] = dp(i - 1, j) * (1 - p[i]) + dp(i - 1, j - 1) * p[i]
    return memo[i][j]


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


print("{}".format(ans))

Submission status: Runtime Error

Solution code:
def backtrack(ans, ip, heads, tails, N):
    if (N==0):
        ans.append(ip);
        return;
    if heads>0: backtrack(ans,ip+'H',heads-1,tails,N-1);
    if tails>0: backtrack(ans,ip+'T',heads,tails-1,N-1);
    return;

def solve(prob, N):
    heads=N;
    tails=N//2;
    if (N%2==0): tails=N//2-1 
    ans=[];
    backtrack(ans,"",heads,tails,N);
    count=0.0;
    for s in ans:
        temp=1;
        for i in range(N):
            if (s[i]=='H'): temp=temp*prob[i];
            else: temp=temp*(1-prob[i]);
        count+=temp;
    return count;


N=int(input())
prob=[float(i) for i in (input().split())];
ans=solve(prob,N);
print(ans);

Submission status: Runtime Error

Solution code:
from itertools import combinations
import numpy as np 
N =int(input())
P = list(map(int,input().split()))
p = 0
for i in range(int(np.ceil(N/2)),N+1):
    for comb in combinations(range(N), i):
        #print(i,comb)
        p += np.prod([P[j] for j in comb] + [1-P[j] for j in set(range(N)).difference(comb)])
print(p)

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline
#import math
#import numpy as np
N = int(input())
#= input()
#= map(int, input().split())
p = list(map(float, readline().split()))
#= [input(), input()]
#= [list(map(int, input().split())) for _ in range(N)]
#= {i:[] for i in range(N)}

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

dp[0][0] = 1

for i, p in enumerate(p, 1):
    pp = 1 - p
    dpij = dp[i][j]
    dpi = dp[i - 1]
    for j in range(i + 1):
        if j == 0:
            dpij = dpi[j] * pp
        elif j == i:
            dpij = dpi[j - 1] * p
        else:
            dpij = dpi[j - 1] * p + dpi[j] * pp

res = 0.0
n = N // 2 + 1

for cnt in dp[-1][n:]:
    res += cnt

print(res)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
#import math
#import numpy as np
N = int(input())
#= input()
#= map(int, input().split())
p = list(map(float, input().split()))
#= [input(), input()]
#= [list(map(int, input().split())) for _ in range(N)]
#= {i:[] for i in range(N)}

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

dp[0][0] = 1

for i, p in enumerate(p, 1):
    pp = 1 - p
    dpij = dp[i][j]
    dpi = dp[i - 1]
    for j in range(i + 1):
        if j == 0:
            dpij = dpi[j] * pp
        elif j == i:
            dpij = dpi[j - 1] * p
        else:
            dpij = dpi[j - 1] * p + dpi[j] * pp

    dp[i][j] = dpij
    
res = 0.0
n = N // 2 + 1

for cnt in dp[-1][n:]:
    res += cnt

print(res)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
#import math
#import numpy as np
N = int(input())
#= input()
#= map(int, input().split())
p = list(map(float, input().split()))
#= [input(), input()]
#= [list(map(int, input().split())) for _ in range(N)]
#= {i:[] for i in range(N)}

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

dp[0][0] = 1

for i, p in enumerate(p, 1):
    pp = 1 - p
    dpij = dp[i][j]
    dpi = dp[i - 1]
    for j in range(i + 1):
        if j == 0:
            dpij = dpi[j] * pp
        elif j == i:
            dpij = dpi[j - 1] * p
        else:
            dpij = dpi[j - 1] * p + dpi[j] * pp

res = 0.0
n = N // 2 + 1

for cnt in dp[-1][n:]:
    res += cnt

print(res)

Submission status: Runtime Error

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_i
import math
N = int(input())
P_List = list(map(float,input().split()))
dp = [[] * N for i in range(N+1)]
std = math.ceil(N/2)
for i in range(N+1):
    if i == 0:
        dp[0].append(1)
    else:
        Current_P = P_List[i - 1]
        for j in range(i + 1):
            if (N - i + j) < std:
                dp[i].append(0)
            elif j == 0:
                dp[i].append(dp[i - 1][j]*(1 - Current_P),10)
            elif j != i:
                dp[i].append((dp[i - 1][j]*(1 - Current_P)) + (dp[i - 1][j - 1]*Current_P),10)
            else:
                dp[i].append(dp[i - 1][j - 1]*Current_P,10)
    
print(sum(dp[N]))

Submission status: Runtime Error

Solution code:

n=int(input())
arr = list(map(float,input().split()))
dp = [[-1]*(3001) for i in range(3001)]

def func(n,x):
    if x==0:
        return 1
    if dp[n][x]>-0.9:
        return dp[n][x]  
    if n==0:
        return 0
    
    dp[n][x] = (arr[n-1])*func(n-1,x-1) + (1-arr[n-1])*func(n-1,x)
    return dp[n][x]

print("%0.10f"%func(n,(n+1)//2))

Submission status: Runtime Error

Solution code:
n=int(input())
arr = list(map(float,input().split()))
dp = [[-1]*(3001) for i in range(3001)]

def func(n,x):
    if x==0:
        return 1
    if dp[n][x]>-0.9:
        return dp[n][x]  
    if n==0:
        return 0
    
    dp[n][x] = (arr[n-1])*func(n-1,x-1) + (1-arr[n-1])*func(n-1,x)
    return dp[n][x]

print("%0.10f"%func(n,(n+1)//2))

Submission status: Runtime Error

Solution code:
n=int(input())
arr = list(map(float,input().split()))
dp = [[-1]*(3001) for i in range(3001)]

def func(n,x):
    if x==0:
        return 1
    if dp[n][x]>-0.9:
        return dp[n][x]
    
    if n==0:
        return 0
    
    dp[n][x] = (arr[n-1])*func(n-1,x-1) + (1-arr[n-1])*func(n-1,x)
    return dp[n][x]

print("%0.10f"%func(n,(n+1)//2))

Submission status: Runtime Error

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

def func(n,x):
    if n==0 and x==0:
        return 1
    if dp[n][x]!=-1:
        return dp[n][x]
    
    if n==0 and x!=0:
        return 0
    
    if x==0 and n!=0:
        return 1
    
    dp[n][x] = (arr[n-1])*func(n-1,x-1) + (1-arr[n-1])*func(n-1,x)
    return dp[n][x]

print("%0.10f"%func(n,(n+1)//2))

Submission status: Runtime Error

Solution code:
N = int(input())
p_list = 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_list[i-1])
        if j > 0:
            dp[i][j] += dp[i-1][j-1] * p_list[i-1]
            
start = N//2 + 1
for p in dp[N][start:]:
    ans += p
print(ans)