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:
from itertools import accumulate
n = int(input())
p = list(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(prob_sum)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
n = int(input())
p = list(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: Time Limit Exceeded

Solution code:
N = int(input())
p = tuple(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])

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

Submission status: Time Limit Exceeded

Solution code:
N  = input()
N = int(N)

probs = []

probs = input().split(' ')

probs = [float(x) for x in probs]

dp = []

for i in range(0,N+1):
	temp = [-99] * (N+1)
	dp.append(temp)

dp[0][0] = 1.0

for n in range(0,N+1):
	for m in range(0,N+1):
		if(n == 0 and m != 0):
			dp[n][m] = 0
		else:
			if(n!=0 and m==0):
				dp[n][m] = (1-probs[n-1])*(dp[n-1][m])

			elif(n != 0 and m != 0):
				dp[n][m] = (probs[n-1]*dp[n-1][m-1]) + ((1-probs[n-1])*(dp[n-1][m]))

ans = 0

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

Submission status: Time Limit Exceeded

Solution code:
N  = input()
N = int(N)

probs = []

probs = input().split(' ')

probs = [float(x) for x in probs]

dp = []

for i in range(0,N+1):
	temp = [-99] * (N+1)
	dp.append(temp)

dp[0][0] = 1.0

for n in range(0,N+1):
	for m in range(0,N+1):
		if(n == 0 and m != 0):
			dp[n][m] = 0
		elif(m == 0 and n != 0):
			x = 1
			for i in range(0,n):
				x = x *  (1-probs[i])
				dp[n][m] = x
		else:
			if(n != 0 and m != 0):
				dp[n][m] = (probs[n-1]*dp[n-1][m-1]) + ((1-probs[n-1])*(dp[n-1][m]))

ans = 0

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

Submission status: Time Limit Exceeded

Solution code:
inp = lambda cast=int: list(map(cast, input().split()))
printf = lambda s='', *args, **kwargs: print(str(s).format(*args), flush=True, **kwargs)
n, = inp()
A = [0.0] + inp(float)
dp = [[0.0 for _ in range(n + 1)] for _ in range(n + 1)]
res = 0.0
for i in range(n + 1):
    for j in range(n + 1):
        if i == 0:
            dp[i][j] = 1 if j == 0 else 0
        elif j == 0:
            dp[i][j] = dp[i-1][j] * (1 - A[i])
        else:
            dp[i][j] = dp[i-1][j] * (1 - A[i]) \
                       + dp[i-1][j-1] * A[i]
        if i == n and j > n/2:
            res += dp[i][j]
printf(res)

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

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

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

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# coding: utf-8

def main():
    #raw = ["3", "0.30 0.60 0.80"]
    #raw = ["1", "0.50"]
    #raw = ["5","0.42 0.01 0.42 0.99 0.42"]
    #N = int(raw[0])
    #ps = list(map(float, raw[1].split()))
    import sys
    N = int(sys.stdin.readline().split()[0])
    ps = list(map(float, sys.stdin.readline().split()))
    memo = [[0] * (N + 1) for _ in range(N + 1)]
    memo[0][0] = 1.0
    for i in range(N):
        for j in range(i + 1):
            memo[i + 1][j] += memo[i][j] * (1.0 - ps[i])
            memo[i + 1][j + 1] += memo[i][j] * ps[i]
        #for xs in memo:
        #    print("{:.2f} {:.2f} {:.2f} {:.2f}".format(*xs))
        #print("")

    ans = 0.0
    #for xs in memo:
    #    print("{:.2f} {:.2f} {:.2f} {:.2f}".format(*xs))
    for i in range(N//2+1, N + 1):
        ans += memo[N][i]
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


def dp_solve(n):
    dp = [[0.0]*(n+1) for _ in range(n+1)]
    dp[0][0] = 1.0
    pi = list(map(float, stdin.readline().split()))

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

    return dp[-1]


if __name__ == "__main__":
    n = int(input())
    res = dp_solve(n)
    m = int(n/2+1)
    print(sum(res[m:]))

Submission status: Time Limit Exceeded

Solution code:
def func(num,arr):
  dp=[1]*(n+1)
  dp[0]=(1-arr[0])
  dp[1]=arr[0]
  for i in range(1,n):
    dp[i+1]=dp[i]*arr[i]
    for j in range(1,i+1):
      dp[i+1-j]=dp[i-j]*arr[i]+dp[i+1-j]*(1-arr[i])
    dp[0]=dp[0]*(1-arr[i])
  return dp

n=int(input())
arr=list(map(float,input().split()))
dp=func(n,arr)
ans=0
for i in range(int(n/2)+1,n+1):
  ans+=dp[i]
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_i

I - Coins

"""
import collections


def solve(ps):
    dp = collections.defaultdict(float)
    dp[0] = 1.0
    for p_i in ps:
        for head_count in reversed(range(N + 1)):
            dp[head_count] = p_i * dp[head_count - 1] + (1 - p_i) * dp[head_count]

    more_than_half = (N + 2) // 2
    res = sum(dp[head_count] for head_count in range(more_than_half, N + 1))
    return res
 

N = int(input())
ps = [float(s) for s in input().split()]
res = solve(ps)
print(res)

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[投げた枚数][表になった回数] = 確率
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
for j in range(N+1):
  if j >= N/2:
    ans += dp[-1][j]
print(ans)

Submission status: Time Limit Exceeded

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

dp = [[0]*(N+1) for _ in range(N+1)]
dp[0][0] = 1
#dp[i][j] i枚投げた時 j枚 表が出る確率
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+1)//2:]))

Submission status: Time Limit Exceeded

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

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

print(num)

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

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

print(num)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

def main(n, lst_p):
    # dp[j] := 表が j 枚となる確率
    # dp[j] = dp[j-1]*p[i] + dp[j]*(1-p[i])
    dp = [0.0] * (N+1)
    # 初期条件
    dp[0]= 1.0

    for i in range(N):
        # 更新前の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)

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

main(N, lst_p)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

    # dp[j] := 表が j 枚となる確率
    # dp[j] = dp[j-1]*p[i] + dp[j]*(1-p[i])
    dp = [0.0] * (N+1)
    # 初期条件
    dp[0]= 1.0

    for i in range(N):
        # 更新前のdpを更新に使う。
        dp_before_update = list(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: Time Limit Exceeded

Solution code:
import sys

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

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

    # dp[j] := 表が j 枚となる確率
    # dp[j] = dp[j-1]*p[i] + dp[j]*(1-p[i])
    dp = [0.0] * (N+1)
    # 初期条件
    dp[0]= 1.0

    for i in range(N):
        # 更新前の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: Time Limit Exceeded

Solution code:
import sys

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

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

    # dp[j] := 表が j 枚となる確率
    # dp[j] = dp[j-1]*p[i] + dp[j]*(1-p[i])
    dp = [0] * (N+1)
    # 初期条件
    dp[0]= 1.0

    for i in range(N):
        # 更新前の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: Time Limit Exceeded

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

    print(ans)

main()

Submission status: Time Limit Exceeded

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

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:

power = pow(10,-40)
n = int(input())

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

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

print('%.15f'%ans)

Submission status: Time Limit Exceeded

Solution code:


n = int(input())

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

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

print('%.15f'%ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
p_ls = [float(i) for i in input().split()]
memo_ls = [[0 for i in range(N+1)] for j in range(N)]

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import ceil

input = sys.stdin.readline

# dp[i][j] = i枚目までに表がj枚出る確率
# dp[i][j] = dp[i - 1][j - 1] * p_i + dp[i - 1][j] * (1 - p_i)

N = int(input())
p = [float(x) for x in input().split()]
dp = [[0.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(i + 2):
        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])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import ceil

input = sys.stdin.readline

# dp[i][j] = i枚目までに表がj枚出る確率
# dp[i][j] = dp[i - 1][j - 1] * p_i + dp[i - 1][j] * (1 - p_i)

N = int(input())
p = [float(x) for x in input().split()]
dp = [[0.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):
        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])

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

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, p):
    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 + 1):
            dp[i + 1][j] = dp[i][j - 1] * p[i] + \
                dp[i][j] * (1 - p[i])
    return(sum(dp[n][n // 2 + 1:]))

n = int(input()) # n: odd, 1 <= n <= 2999
p = list(map(float, input().split())) # 0 < pi[i] < 1
print(f(n, p))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys,bisect
input = sys.stdin.readline
n = int(input())
p = tuple(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(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]

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

Submission status: Time Limit Exceeded

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):
    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(dp, sep='\n')        
ans = 0
for j in range(n//2+1, n+1):
    ans += dp[n][j]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

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

Submission status: Time Limit Exceeded

Solution code:

def get_probability(P, N):
    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] = DP[i-1][0]*(1-P[i-1])
        DP[0][i] = 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-1][j-1]*P[i-1]
    prob = 0
    for i in range(N//2+1, N+1):
        prob += DP[N][i]
    return prob
N = int(input())
P = [float(s)for s in input().split(" ")]
result = get_probability(P, N)
print("{}".format(result))

Submission status: Time Limit Exceeded

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

dp = [[0 for j 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] += 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/2 :
        ans += dp[N][i]
print(ans)

Submission status: Time Limit Exceeded

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

DP = [[0] * (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])

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

Submission status: Time Limit Exceeded

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

#dp[投げたコイン枚数][表のコイン枚数] 
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])
  dp[i][i] = dp[i-1][i-1]*p[i-1]
  for j in range(1,i):
    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: Time Limit Exceeded

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

N = int(input())
P = list(map(float, 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+1] += dp[i][j] * P[i]
        dp[i+1][j] += dp[i][j] * (1.0 - P[i])

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

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import sys

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n = II()
P = LF()

# dp[i]: i枚のコインが表になる確率
dp = [1]

# 調和級数
# O(NlogN)
for i in range(n):
    tmp = [0] * (i + 2)
    p = P[i]
    q = 1 - P[i]
    for j in range(i + 1):
        tmp[j] += dp[j] * q
        tmp[j + 1] += dp[j] * p
    dp = tmp

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

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import sys

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n = II()
P = LF()

# dp[i][j]: i番目のコインまで投げた時，j枚のコインが表になる確率
dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1

# 調和級数
# O(NlogN)
for i in range(n):
    for j in range(i + 1):
        if dp[i][j] == 0:
            continue
        # P[i]が裏
        dp[i + 1][j] += dp[i][j] * (1 - P[i])
        # P[i]が表
        dp[i + 1][j + 1] += dp[i][j] * P[i]

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]
    P = []
    input_raw = read_func().strip().split()
    for i in range(N):
        P.append(float(input_raw[i]))

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

            #dp[i][j] += p[i] * dp[i - 1][j - 1] + (1 - p[i])

    count = 0L
    for j in range(N/2 + N%2, N + 1):
        count += dp[N][j]
    print count
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = list(map(float, input().split()))
prob = [0.0] * (n + 1)
prob[0] = 1.0
for i in range(n):
	p0 = 1 - p[i]
	p1 = p[i]
	for j in range(n, 0, -1):
		prob[j] = prob[j - 1] * p1 + prob[j] * p0
	prob[0] = prob[0] * p0
pro = 0.0
for i in range((n // 2) + 1, n + 1):
	pro += prob[i]
print(pro)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
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 >= 1:
            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])
            
print(sum(dp[i][n//2+1:]))

Submission status: Time Limit Exceeded

Solution code:


n = input()
p = map(float, raw_input().split())

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=list( int(s[2:]) for s in input().split() )
z=0
res=[100-p[0], p[0]]+[0]*(n//2 - 1)
for i in range(1,n):
    z=z+1
    for j in range(len(res)-1, 0, -1):
        res[j]=(res[j]*(100-p[i]) + (res[j-1]*p[i]) )
    res[0]=res[0]*(100-p[i])
    if z==10:
        for x in res: x=x//100**5
        z=5
print( 1-(sum(res[:1+n//2])/(100**(z+1)) ) )

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=list( float(s) for s in input().split() )

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n=int(input())
P=np.array(list(map(float,input().split())))
DP=np.zeros(n+1)
DP[0]=1.0

for i in range(n):
  D=np.zeros(n+1)
  p=P[i]
  for j in range(i+2):
    D[j] = DP[j-1] * p + DP[j] * (1-p)
  DP=D
print(sum(DP[n//2+1:]))

Submission status: Time Limit Exceeded

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

DP = [[0 for n 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):
    use = P[i]
    DP[i][0] = DP[i-1][0] * (1-use)
    for j in range(1, i+2):
        DP[i][j] = DP[i-1][j] * (1-use) + DP[i-1][j-1] * use

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

Submission status: Time Limit Exceeded

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

DP = [[0 for n 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):
    use = P[i]
    dontuse = 1 - use
    for j in range(N):
        if j == 0: DP[i][0] = DP[i-1][0] * dontuse
        else:
            DP[i][j] = DP[i-1][j] * dontuse + DP[i-1][j-1] * use
    if i == N-1: DP[N-1][N] = DP[N-2][N-1] * use

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

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(1, N+1, 2)]

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

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

for i in range(n+1):
    for j in range(i+1):
        if i>0 and j>0:
            dp[i][j]+=p[i-1]*dp[i-1][j-1]
        if i>0:
            dp[i][j]+=(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: Time Limit Exceeded

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):
        if j + 1 <= 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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = [float(a) for a in input().split()]

pre = []
post = [1]

for i in range(N):
    pre = post
    post = [0] * (i+2)
    for j in range(i+2):
        if j > 0:
            post[j] += pre[j-1] * P[i]
        if j <= i:
            post[j] += pre[j] * (1-P[i])

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