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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)

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: Time Limit Exceeded

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

dp = [[0.0 for _ in range(N + 1)] for _ in range(N + 1)]
dp[1][1] = p_list[0]
dp[1][0] = 1 - p_list[0]

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

print("{:.10f}".format(sum(dp[N][N // 2 + 1:])))

Submission status: Time Limit Exceeded

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

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

for j in range(A,N+1):
   ans += dp[N-1][j]
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
N = int(stdin.readline())
p = list(map(float, stdin.readline().split()))
M = N//2 + 1
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
# dp[coin number][top coin number]
dp[1][0] = 1.0-p[0]
dp[1][1] = p[0]
for i in range(3, N+1):
    if i % 2 == 0:
        continue
    for j in range(N+1):
        dp[i][j] = dp[i-2][j]*(1.0-p[i-1])*(1.0-p[i-2])
        if j >= 1:
            dp[i][j] += dp[i-2][j-1]*(p[i-1]*(1.0-p[i-2])+(1.0-p[i-1])*p[i-2])
        if j >= 2:
            dp[i][j] += dp[i-2][j-2]*p[i-1]*p[i-2]
        # dp[i][j] = dp[i-2][j]*(1.0-p[i-1])*(1.0-p[i-2]) + \
        #    dp[i-2][j-1]*(p[i-1]*(1.0-p[i-2])+(1.0-p[i-1])*p[i-2]) + \
        #    dp[i-2][j-2]*p[i-1]*p[i-2]
print(sum(dp[N][N//2+1:]))

Submission status: Time Limit Exceeded

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

t=N//2+1 if N%2 else N//2
ans=0
for i in range(t,N+1):
    ans+=dp[N][i]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(float,input().split()))
lista = [1.0-a[0],a[0]]
ans = []
ans.append(lista)
for i in range(N-1):
  lista = []
  lista.append(ans[i][0]*(1.0-a[i+1]))
  for j in range(i+1):
    lista.append(ans[i][j]*(a[i+1])+ans[i][j+1]*(1.0-a[i+1]))
  lista.append(ans[i][i+1]*a[i+1])
  ans.append(lista)
ai = int((N+1)/2)
LIST = lista[ai:]
print(sum(LIST))

Submission status: Time Limit Exceeded

Solution code:
def i_coins(N, P):
    """
    N枚の番号が振られたコインがある。i番目のコインを投げたときに
    表が出る確率はp_i, 裏が出る確率は1-p_iである。
    N枚のコインをすべて投げるとき、表の枚数が裏の枚数を上回る確率を求めよ。
    """
    # dp[i][j]: コインをi枚使ったとき、表がj枚である確率
    dp = [[0.0] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 1.0  # これで初期化(0枚投げて表が0枚である確率は考えられないが)
    for i in range(1, N + 1):
        # 表が出た回数が投げたコインの枚数を上回ることはありえない
        for j in range(i + 1):
            # i枚使ってj枚表が出る確率
            # = i-1枚使ってj-1枚表が出る確率 * i枚目が表である確率
            # + i-1枚使ってj枚表が出る確率 * i枚目が裏である確率
            dp[i][j] = (dp[i - 1][j - 1] * P[i - 1] * int(j >= 1)
                        + dp[i - 1][j] * (1.0 - P[i - 1]))

    ans = 0.0
    for i in range(N // 2 + 1, N + 1):
        ans += dp[N][i]  # N枚使ってN//2+1枚以上表が出る確率を足し合わせると解
    ans = round(ans, 11)  # round()は正確には偶数への丸めだが、使う
    return ans

N = int(input())
P = [float(i) for i in input().split()]
print(i_coins(N, P))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = list(map(float, input().split()))
dp = [[0 for _ in range(n+1)] for _ in range(n)]
#dp[i][j]: iまで投げてj枚表の確率
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])
		else:
			dp[i][j] = dp[i-1][j] * (1 - p[i]) + dp[i-1][j-1] * p[i]

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

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())
P = list(map(float, input().split()))

# suml = [[1 for _ in range(N)] for _ in range(N+1)]
suml = [[1 for x in range(round+1)] for round in range(N+1)]
# print(sum(p) / 3)

# for foreachCoinIndex,p in enumerate(P):
for e,p in enumerate(P):
    for (es, s),_ in zip(enumerate(suml[e]), range(e+1)):

        if (es == 0):
            suml[e+1][es]   = suml[e][es] * (1-p)
        else:
            suml[e+1][es]   += suml[e][es] * (1-p)

        suml[e+1][es+1] = suml[e][es] * p


# for i in range(len(suml)):
#     print(suml[i])
#     # print(sum(suml[i][:len(suml[i])//2+1]))
#     print(sum(suml[i]))
sumA = suml[N][:len(suml[N])//2-1:-1]
sumA = sum(sumA)
print(sumA)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

dp = [0] * (N+1)
dp[0] = 1
for p in ps:
    pp = 1 - p
    for j in reversed(range(N+1)):
        dp[j] = dp[j]*pp + dp[j-1]*p

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

Submission status: Time Limit Exceeded

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

NOW=[1]

for i in range(N):
    NEXT=[0]*(i+2)

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

    NOW=NEXT
    #print(NOW)

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

Submission status: Accepted

Solution code:
n = int(raw_input())
p = list(map(float, raw_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 < i+1:
            dp[i][j] += dp[i-1][j]*(1-p[i])
        if j > 0:
            dp[i][j] += dp[i-1][j-1] * p[i]

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

Submission status: Accepted

Solution code:
N = int(input())

p_list = 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(N):
    for j in range(i+1):
        dp[i+1][j+1] += dp[i][j] * p_list[i]
        dp[i+1][j] += dp[i][j] * (1.0 - p_list[i])
    #print(dp[i])

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin
def input():
    return stdin.readline().strip()

def main():
    n = int(input())
    probabilities = list(map(float, input().split()))

    # dp[i] = P(i heads coins)
    dp = [0.0] * (n//2 + 3)
    dp[0] = 1.0
    for p in probabilities:
        dp[n//2 + 1] += dp[n//2] * p
        for j in range(n//2 + 1)[::-1]:
            dp[j] = dp[j] * (1 - p) + dp[j-1] * p

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

main()

Submission status: Accepted

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

#import
#import math
#import numpy as np
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, p in enumerate(P, 1):
    for j in range(i + 1):
        if j == 0:
            dp[i][j] = dp[i - 1][j] * (1 - p)

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

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

print(ans)

Submission status: Accepted

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

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

if __name__=="__main__":
    n,p= getval()
    main(n,p)

Submission status: Accepted

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

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

if __name__=="__main__":
    n,p= getval()
    main(n,p)

Submission status: Accepted

Solution code:
import sys
import math


# \n
def input():
    return sys.stdin.readline().rstrip()


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

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

            dp[i] = dp[i]*(1-p)
            if i ==0:
                continue
            dp[i] +=dp[i-1] *p

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






if __name__ == "__main__":
    main()

Submission status: Accepted

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

N = int(input())

def li():
    return [float(x) for x in input().split()]

P = li()
# dp[i][j]: i番目のコインを投げた時に、表がj枚となる確率
dp = [[0] * (N+1) for _ in range(N)]

dp[0][1], dp[0][0] = P[0], 1 - P[0]

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

total = 0
for j in range(N+1):
    if 2 * j > N:
        total += dp[N-1][j]

print(total)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

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

Submission status: Accepted

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

dp = [[0]*3100 for _ in range(3100)]

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
P = list(map(float, input().split()))
DP = np.zeros(N+2)
DP[0] = 1
for i, p in enumerate(P, 1):
    DP = DP * (1 - p) + np.roll(DP, 1) * p

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

ans = 0

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

print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

# dp[i][j]: 最初の i 枚のコインを投げたとき、表が j 回出る確率
dp = [[0]*(N+1) for _ in range(N+1)]

# 初期条件
# コインを 0 枚投げたとき、表が 0 回出る確率は 1
dp[0][0] = 1

# コインを i 枚投げたとき
for i in range(1,N+1):
    # 表が j 回出たとき
    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-P[i-1])
    
# 半分以上表ときの確率
ans = 0
for j in range(N//2 + 1,N+1):
    ans += dp[N][j]
print(ans)

Submission status: Accepted

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

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

main()

Submission status: Accepted

Solution code:
n= int(input())
p =[float(x) for x in 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(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: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

# from pprint import pprint

def recur(parr, curp, curi, heads):
    # if dp[curi][heads] != -1:
    # return dp[curi][heads]
    if curi >= len(parr):
        if heads >= len(parr)//2 + 1:
            return curp
        else:
            return 0

    return (recur(parr, curp*parr[curi], curi+1, heads+1)
            + recur(parr, curp*(1-parr[curi]), curi+1, heads))

n = int(input())

parr = [float(i) for i in input().split(' ')]

# print(recur(parr, 1, 0, 0))

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

for i in range(n):
    for j in range(i+1, -1, -1):
        # heads
        heads = dp[j-1] if j > 0 else 0
        # tails
        tails = dp[j]
        dp[j] = heads*parr[i-1] + tails*(1-parr[i-1])

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

Submission status: Accepted

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

# from pprint import pprint

def recur(parr, curp, curi, heads):
    # if dp[curi][heads] != -1:
    # return dp[curi][heads]
    if curi >= len(parr):
        if heads >= len(parr)//2 + 1:
            return curp
        else:
            return 0

    return (recur(parr, curp*parr[curi], curi+1, heads+1)
            + recur(parr, curp*(1-parr[curi]), curi+1, heads))

n = int(input())

parr = [float(i) for i in input().split(' ')]

# print(recur(parr, 1, 0, 0))

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(i, -1, -1):
        # heads
        heads = dp[i-1][j-1] if j > 0 else 0
        # tails
        tails = dp[i-1][j]
        dp[i][j] = heads*parr[i-1] + tails*(1-parr[i-1])

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    P = [float(i) for i in input().split()]
    dp = [[0]*(N+1) for _ in range(N+1)]
    dp[1][1] = P[0]
    dp[1][0] = 1 - P[0]
    for i in range(2, N+1):
        p = P[i-1]
        for j in range(i+1):
            p1 = dp[i-1][j-1] * p if j != 0 else 0
            p2 = dp[i-1][j] * (1 - p)
            dp[i][j] = p1 + p2
    ans = 0
    for j in range(0--N//2, N+1):
        ans += dp[N][j]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
INF=float('inf')

n=int(input())
P=list(map(float,input().split()))#0

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

Submission status: Accepted

Solution code:
INF=float('inf')

n=int(input())
P=list(map(float,input().split()))#0

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

for i in range(n+1):
  if i==0:
    dp[0][0]=1
  else:
    dp[i][0]=(1-P[i-1])*dp[i-1][0]

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

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

Submission status: Accepted

Solution code:
def coins(n,prob):
    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-prob[i-1])
            else:
                dp[i][j] = dp[i-1][j]*(1-prob[i-1])+dp[i-1][j-1]*prob[i-1]
    total = 0
    for i in range(n,n//2,-1):
        total+= dp[n][i]
    return total

n = int(input())
prob = list(map(float,input().split()))
print(coins(n,prob))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")


# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input


def out(var): sys.stdout.write(str(var))  # for fast output, always take string


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  # as stdout.write always print sring.


def testcase(t):
    for p in range(t):
        solve()


from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count



from sys import setrecursionlimit
setrecursionlimit(1000000)



def solve():
    n=int(inp())
    ar=[float(i) for i in inp().strip().split(" ")]
    dp=[[0 for _ in range(n+5)] for i in range(n+5)]
    dp[1][0]=1-ar[0]
    dp[1][1]=ar[0]
    for i in range(2,n+1):
        dp[i][0]=dp[i-1][0]*(1-ar[i-1])
    for i in range(2,n+1):
        for j in range(1,n+1):
            if j>i:
                break
            dp[i][j]=dp[i-1][j]*(1-ar[i-1])+dp[i-1][j-1]*ar[i-1]
    s=0
    for i in range(n//2 +1 ,n+1):
        s+=dp[n][i]

    print(s)






solve()

Submission status: Accepted

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):
    dp(i, i)
    dp(i, n)

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


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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n = int(input())
temparr = input()
temparr = temparr.split()
arr = []
for i in temparr:
    arr.append(float(i))
#print(arr)
nn = n + 1 
temparr = [0 for _ in range(nn)]
dp = [temparr[::] for _ in range(nn)]
#print(dp)

dp[0][0] = 1 

for i in range(1, nn):
    for j in range(0, nn):
        if j == 0 :
            dp[i][j] = dp[i - 1][j] *(1 - arr[i - 1])
            continue 
        else:
            dp[i][j] = dp[i - 1][j - 1] * arr[i - 1] + dp[i - 1][j] * (1 - arr[i - 1])
lastarr = dp[-1]

half = n // 2 + 1 

ans = 0 
for i in range(half, nn):
    ans += lastarr[i]
print(ans)

Submission status: Accepted

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

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

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