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: Runtime Error

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

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

Submission status: Runtime Error

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


print(sum(p)/n)

Submission status: Runtime Error

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


print(sum(ls)/n)

Submission status: Runtime Error

Solution code:
def getCombi(h,t,n,s):
    if len(s)==n:
        combs.append(s)
    if h>0:
      getCombi(h-1,t,n,s+'h')
    if t>0:
      getCombi(h,t-1,n,s+'t')


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

combs=[]
for i in range(heads,n+1):
    s = ''
    getCombi(i,n-i,n,s)
totalProb=0
for y in combs:
    subsum=1
    for j in range(len(y)):
        if y[j]=='h':
            subsum*=p[j]
        else:
            subsum*=(1-p[j])
    totalProb+=subsum
print(totalProb)

Submission status: Runtime Error

Solution code:
import functools
import operator
n = int(input())
p = list(map(float, input().split()))
half = n // 2 + 1

dp = [[None] * (n + 1) for _ in range(n + 1)]
def dfs(n=half, depth=n - 1):
    if depth < 0 or (n - 1) > depth:
        return 0

    if dp[n][depth] is not None:
        return dp[n][depth]

    if n == 0:
        r = functools.reduce(operator.mul, map(lambda x: 1 - x, p[:depth + 1]))
    elif (n - 1) == depth:
        r = functools.reduce(operator.mul, p[:depth + 1])
    else:
        r = dfs(n - 1, depth - 1) * p[depth] + dfs(n, depth - 1) * (1 - p[depth])
    dp[n][depth] = r
    return r

print(sum(dfs(i) for i in range(half, n + 1)))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()
INL=list(map(float, LS()))
DP=[0.0]*(N+1)
DP[0]=1.0

for p in INL:
    for i in reversed(range(N)):
        DP[i+1] = DP[i+1]*(1.0-p) + DP[i]*p

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

Submission status: Runtime Error

Solution code:
from itertools import accumulate
n = int(input())
p = [*map(float, input().split())]
dp = p.copy()
t = 1
for i in p:
    t *= 1 - i
ps = list(accumulate([t * i / (1 - i) for i in p]))
prob_sum = 0
for i in range(1, n):
    for j in range(n - i):
        dp[j] = p[j] * (ps[n - i] - ps[j]) / (1 - p[j])
        ps[j] = (ps[j - 1] if j > 0 else 0) + dp[j]
    if i + 1 > n // 2:
        prob_sum += ps[n - 1 - i]
if n == 1:
    print(p[0])
else:
    print(round(prob_sum, 9))

Submission status: Runtime Error

Solution code:
import sys

# input処理を高速化する
input = sys.stdin.readline

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

    # dp[j] := 表が j 枚となる確率
    # dp[j] = dp[j-1]*p[i] + dp[j]*(1-p[i]) ただしdp[j]が重複していることに注意
    dp = [0.0] * (N+1)
    # 初期条件
    dp[0]= 1.0

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

        # 更新前のdpを更新に使う。
        dp_before_update = dp[:]
        for j in range(N+1):
            dp[j] = (dp_before_update[j-1] * lst_p[i]) + (dp_before_update[j] * (1 - lst_p[i]))
    
    ans = sum(dp[(N//2+1):])

    print(ans)

main()

Submission status: Runtime Error

Solution code:
import sys

# input処理を高速化する
input = sys.stdin.readline

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

    # dp[i][j] := 最初の i 枚のコインを投げたときに、表が j 枚となる確率
    # 次のコインが表: dp[i+1][j+1] += dp[i][j]∗p[i]
    # 次のコインが裏: dp[i+1][j] += dp[i][j]∗(1.0−p[i])
    dp = [[0] * (N+1) for i in range(N+1)]

    # 初期条件
    dp[0][0] = 1.0

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

    print(ans)

main()

Submission status: Runtime Error

Solution code:
n=int(input())
p=list(map(float,input().split()))
result = [[-1.]*n for _ in range(n)]

# i番目のコインまででj枚が表のときの、全体として表が裏より多くなる確率
def dp(i,j):
    if i == n:
        if j > i-j:
            return 1
        else:
            return 0
    if result[i][j] != -1:
        return result[i][j]
    
    res1 = dp(i+1,j+1) * p[i]
    res2 = dp(i+1,j) *(1-p[i])
    result[i][j] = res1+res2
    return result[i][j]

print(dp(0,0))

Submission status: Runtime Error

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

def foo(i,h,t,p):
	if i==n-1:
		if h>t:
			return p
		else:
			return 0
	return foo(i+1,h+1,t,p*a[i+1])+foo(i+1,h,t+1,p*(1-a[i+1]))

print(foo(-1,0,0,1))

Submission status: Runtime Error

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

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