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: Wrong Answer

Solution code:
import numpy as np
N = int(input())
p = np.array([0.0] + list(map(float, input().split())))

# コインnまでを投げたとき、表がx枚でる確率
dp = np.zeros((N + 1, N + 1), np.float64)
dp[0, 0] = 1
dp[:, 0] = np.cumprod(1 - p).T
print(np.cumprod(1 - p))
for i in range(1, N + 1):
    dp[i][1:] = dp[i - 1][:-1] * p[i] + dp[i - 1][1:] * (1 - p[i])

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

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
p = np.array([0.0] + list(map(float, input().split())))

# コインnまでを投げたとき、表がx枚でる確率
dp = np.zeros((N + 1, N + 1), np.float32)
dp[0, 0] = 1
dp[:, 0] = np.cumprod(1 - p).T

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

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

Submission status: Wrong Answer

Solution code:
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 - p[0]
DP[0][1] = p[0]

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

Sum = 0.0
for i in range((N+1)//2,N+1):
    Sum += DP[N-1][i]

print(Sum)

Submission status: Wrong Answer

Solution code:
N = int(input())
p = tuple(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(N - 1):
    for j in range(N + 1):
        if DP[i][j] == 0:
            break
        else:
            DP[i+1][j] += DP[i][j] * (1 - p[i+1])
            DP[i+1][j + 1] += DP[i][j] * (p[i+1])

Sum = 0.0
for i in range((N+1)//2,N+1):
    Sum += DP[N-1][i]

print(Sum)

Submission status: Wrong Answer

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(N - 1):
    for j in range(N + 1):
        if DP[i][j] == 0:
            break
        else:
            DP[i+1][j] += DP[i][j] * (1 - p[i+1])
            DP[i+1][j + 1] += DP[i][j] * (p[i+1])

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

print(Sum)

Submission status: Wrong Answer

Solution code:
import numpy as np
n=int(input())
s=list(map(float,input().split()))
a=[0 for _ in range(n+1)]
p = [0 for _ in range(n+1)]
a[0]=1
for i in range(n):
    k=s[i]
    for j in range(len(a)):
        p[j] = a[j]*(1-k)
    for j in range(1,len(a)):
        p[j] += a[j-1]*k
    a = p
print(sum(a[n//2+1:]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import decimal,math
# from decimal import Decimal as co
from collections import Counter,defaultdict
from fractions import gcd
from bisect import bisect_right,bisect_left
decimal.getcontext().prec = 5
import sys
sys.setrecursionlimit(1000000)
co=decimal.Decimal
n=int(raw_input())
p = map(float,raw_input().split())
dp = [[co(0)]*(n+1) for i in range(n+1)]
dp[0][0]=co(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-co(p[i-1]))
		else:
			dp[i][j]=dp[i-1][j]*(1-co(p[i-1]))+dp[i-1][j-1]*co(p[i-1])
ans=co(0.0)
for j in range(n/2+1,n+1):
	ans=ans+dp[n][j]
print ans

Submission status: Wrong Answer

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


print(sum(p)/n)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

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

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

Submission status: Wrong Answer

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

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

        if(j!=0):
            dp[j]=dp[j-1]*p[i]+ dp[j]*(1-p[i])
    dp[0]*=(1-p[i])
s=0
#print(dp)
print(sum(dp[((n//2) +1):]))

Submission status: Wrong Answer

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, 9)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7
 
 
def INT_(n): return int(n)-1
 
 
def MI(): return map(int, input().split())
 
 
def MF(): return map(float, input().split())
 
 
def MI_(): return map(INT_, input().split())
 
 
def LI(): return list(MI())
 
 
def LI_(): return [int(x) - 1 for x in input().split()]
 
 
def LF(): return list(MF())
 
 
def LIN(n: int): return [input() for _ in range(n)]
 
 
def LLIN(n: int): return [LI() for _ in range(n)]
 
 
def LLIN_(n: int): return [LI_() for _ in range(n)]
 
 
def LLI(): return [list(map(int, l.split())) for l in input()]
 
 
def I(): return int(input())
 
 
def F(): return float(input())
 
 
def ST(): return input().replace('\n', '')
 
 
def main():
    N = I()
    p = LF()
    # dp[i][j]:=i枚目までで、k枚が表の確率
    dp = [[0] * (N+1) for _ in range(N)]
    dp[0][1] = p[0]
    dp[0][0] = 1-p[0]
    for i in range(1, N):
        for k in range(i+1):
            if k != 0:
                dp[i][k] += dp[i - 1][k - 1] * p[i]
            dp[i][k] += dp[i-1][k]*(1-p[i])
    ans = 0
    for i in range((N + 1) // 2, N + 1):
        ans += dp[N - 1][i]
    #print(*dp, sep="\n")
    print(ans)
 
 
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())

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

dp = [[0.0] * (len(v)+1) for i in range(len(v))]
for x in range(n):
	for a in range(x + 2):
		if x == 0 and a == 0:
			dp[x][a]=v[x]
		elif x == 0 and a == 1:
			dp[x][a]=1-v[x]
		elif a > n/2:
			dp[x][a]=dp[x-1][a]*v[x]
		else:
			dp[x][a]=dp[x-1][a]*v[x]+dp[x-1][a-1]*(1-v[x])
#import numpy
#print(numpy.matrix(dp));			
print(sum(dp[n-1]))

Submission status: Wrong Answer

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

N = int(input())
pn = list(map(float,input().split()))
dp = np.array([0.0] * (N+1))
dp[0] = 1.0
for i in range(N):
    tmp = dp * (1-pn[i])
    tmp[1:] += dp[:-1] * pn[i]
    dp = tmp

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

Submission status: Wrong Answer

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):
    cnt = 0
    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]
        if memo_ls[i][j] == 0:
            cnt += 1
        else:
            cnt = 0
        if cnt > 9:
            break

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

Submission status: Wrong Answer

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):
    cnt = 0
    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]
        if memo_ls[i][j] == 0:
            cnt += 1
        if cnt > 9:
            break

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

Submission status: Wrong Answer

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]
        if memo_ls[i][j] == 0:
            break

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

Submission status: Wrong Answer

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):
        memo_ls[i][j] = memo_ls[i-1][j] * (1 - p_ls[i]) + memo_ls[i-1][j-1] * p_ls[i]
        if memo_ls[i][j] == 0:
            break

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

Submission status: Wrong Answer

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(n):
        if dp[i][j] == 0:
            break
        # 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('{:0.10f}'.format(sum(dp[n][(n + 1) // 2:])))

Submission status: Wrong Answer

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(n):
        if dp[i][j] == 0:
            break
        # 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 + 1) // 2:]))

Submission status: Wrong Answer

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)
print('#p:', p)
print(res)
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(res)
print( 1-(sum(res[:1+n//2])/(100**(z+1)) ) )

Submission status: Wrong Answer

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):
        print(j)
        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: Wrong Answer

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, 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: Wrong Answer

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

Solution code:
n=int(input())
p=[]
for i in input().split():
  p+=[int(i.split(".")[1])]
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]*(100-p[i])
  for j in range(i+1):
    dp[i+1][j+1]=dp[i][j]*p[i]+dp[i][j+1]*(100-p[i])
print(sum([dp[n][i] for i in range((n+1)//2,n+1)])/pow(100,n))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = list(map(float, 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: 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
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])+dp[i-1][j-1]*p[i-1]
        else:
            dp[i][j] = 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:
import numpy as np

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

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

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

Submission status: Time Limit Exceeded

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

N = int(readline())
P = list(map(float,readline().split()))

# dp[i][j] = i枚投げて、表がj枚出ている確率
dp = [[0] * (N + 1) for i in range(N + 1)]
dp[0][0] = 1
for i in range(N):
  for j in range(N):
    dp[i + 1][j] += dp[i][j] * (1 - P[i])
    dp[i + 1][j + 1] += dp[i][j] * P[i]
    
ans = 0
for i in range(N + 1):
  if i > N // 2:
    ans += dp[-1][i]

print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

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):
    for j in range(i+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）
        #print(i, j, dp[i][j])
        #プログラムの仕組み上，iが一つ進むと，100 * 100 = 10**4　ずつスケールが大きくなっていく。10**20で打ち切る。


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

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):
    for j in range(i+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）
        #print(i, j, dp[i][j])
        #プログラムの仕組み上，iが一つ進むと，100 * 100 = 10**4　ずつスケールが大きくなっていく。10**20で打ち切る。


ans = 0

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

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

Submission status: Time Limit Exceeded

Solution code:
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 = [[0 for a in range(3100)] for b in range(3100)]
#dp[i][j] = i枚目までのコインを投げて，表の個数がj枚である確率 * (10**(2*i))

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

for i in range(2, N + 1):
    for j in range(i+1):
        dp[i][j] = (dp[i-1][j-1] * p[i] + dp[i-1][j] * (100-p[i])) // 10 ** max(0, i-10)
        #dp[i][j] = i-1枚目までで表がj-1かつi回目で表　＋　i-1回目までで表がj枚かつi回目で裏（MECE）
        #print(i, j, dp[i][j])
        #プログラムの仕組み上，iが一つ進むと，100 * 100 = 10**4　ずつスケールが大きくなっていく。10**20で打ち切る。


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

Solution code:
# coding: utf-8
# Your code here!
N=int(input())

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
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 = [[0 for a in range(3100)] for b in range(3100)]
#dp[i][j] = i枚目までのコインを投げて，表の個数がj枚である確率 * (10**(2*i))

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

for i in range(2, N + 1):
    for j in range(i+1):
        dp[i][j] = (dp[i-1][j-1] * p[i] + dp[i-1][j] * (100-p[i])) // 10 ** max(0, i-10)
        #dp[i][j] = i-1枚目までで表がj-1かつi回目で表　＋　i-1回目までで表がj枚かつi回目で裏（MECE）
        #print(i, j, dp[i][j])
        #プログラムの仕組み上，iが一つ進むと，100 * 100 = 10**4　ずつスケールが大きくなっていく。10**20で打ち切る。


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

Solution code:
from decimal import Decimal, getcontext

getcontext().prec = 10

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

#print(p)

dp = [[0 for a in range(3100)] for b in range(3100)]
#dp[i][j] = i枚目までのコインを投げて，表の個数がj枚である確率

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

for i in range(2, 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]))
        #dp[i][j] = i-1枚目までで表がj-1かつi回目で表　＋　i-1回目までで表がj枚かつi回目で裏（MECE）
        #print(i, j, dp[i][j])

ans = Decimal(0)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal, getcontext

getcontext().prec = 20

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

#print(p)

dp = [[0 for a in range(3100)] for b in range(3100)]
#dp[i][j] = i枚目までのコインを投げて，表の個数がj枚である確率

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

for i in range(2, 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]))
        #dp[i][j] = i-1枚目までで表がj-1かつi回目で表　＋　i-1回目までで表がj枚かつi回目で裏（MECE）
        #print(i, j, dp[i][j])

ans = Decimal(0)

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

print(ans)

Submission status: Time Limit Exceeded

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

#print(p)

dp = [[0 for a in range(3100)] for b in range(3100)]
#dp[i][j] = i枚目までのコインを投げて，表の個数がj枚である確率

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

for i in range(2, 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]))
        #dp[i][j] = i-1枚目までで表がj-1かつi回目で表　＋　i-1回目までで表がj枚かつi回目で裏（MECE）
        #print(i, j, dp[i][j])

ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

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

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

dp = [[0 for a in range(3100)] for b in range(3100)]
#dp[i][j] = i枚目までのコインを投げて，表の個数がj枚である確率 * (10**(2*i))

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

for i in range(2, N + 1):
    for j in range(i+1):
        dp[i][j] = dp[i-1][j-1] * p[i] + dp[i-1][j] * (100-p[i])
        #dp[i][j] = i-1枚目までで表がj-1かつi回目で表　＋　i-1回目までで表がj枚かつi回目で裏（MECE）
        #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]

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
INF=float('inf')
import numpy as np

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

dp=np.zeros([n+1,n+1], dtype='float128')

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
p = 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 - p[0]
dp[0][1] = p[0]
for i in range(n):
    for j in range(n+1):
        if (i > 0):
            dp[i][j] = dp[i-1][j] * (1.0 - p[i])
            if (j > 0):
                dp[i][j] += dp[i-1][j-1] * p[i]
ans = 0.0
for i in range(math.ceil(n/2), n+1):
    ans += dp[n-1][i]
print(ans)

Submission status: Time Limit Exceeded

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

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
# import numpy as np
starttime = time.time()
# import numpy as np
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    sys.setrecursionlimit(int(pow(10,6)))
    sys.stdin = open("input.txt", "r")
    # sys.stdout = open("../output.txt", "w")
except:
    pass


n=L()[0]
P=list(map(float,input().split()))
# print(P)
dp=[[0 for i in range(n+1)] for j in range(n+1)]
vis=[[0 for i in range(n+1)] for j in range(n+1)]
def rec(p,h):
    if h<0:
        return 0.0
    if p==0:
        return 1.0*(h==0)
    if vis[p][h]:
        return dp[p][h]
    vis[p][h]=1
    dp[p][h]= P[p-1]*rec(p-1,h-1)+(1-P[p-1])*rec(p-1,h)
    return dp[p][h]
total=0
for i in range(n+1):
    t=n-i
    if i>t:
        total+=rec(n,i)
# print(*dp)
print(total)




endtime = time.time()
# print(f"Runtime of the program is {endtime - starttime}")

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
import numpy as np 
N =int(input())
P = list(map(float,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: Time Limit Exceeded

Solution code:
import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())

def main():
    n = ii()
    p = list(map(float, input().split()))
    dp = np.zeros((n+1, n+1), dtype=float)
    dp[0][0] = 1
    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] = p[i-1]*dp[i-1][j-1] + (1-p[i-1])*dp[i-1][j]
    print(np.sum(dp[-1][n//2+1:]))
    

if __name__ == '__main__':
    main()