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:
N = int(input())
p = list(map(float,input().split()))

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

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

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np 

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

if N%2 == 0:
    ans_p = int(N/2)
else:
    ans_p = int((N+1)/2)

dp = np.zeros((N,ans_p+1))
dp[:,0] = [1]*N
dp[0,1] = P[0]

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

print(dp[N-1,int(ans_p)])

Submission status: Time Limit Exceeded

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

l = [0]*(n+1)
l[0] = (1-p[0])
l[1] = p[0]

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

## 制約：Nは奇数
l.reverse()
print(sum([l[i] for i in range((n+1)//2)]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np 

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

dp = np.zeros((N,N+1))
dp[:,0] = [1]*N
dp[0,1] = P[0]

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

if N%2 == 0:
    ans_p = N/2
else:
    ans_p = (N+1)/2
print(dp[N-1,int(ans_p)])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
P=list(map(float,input().split()))
C=[[0.00]*(N+1) for i in range(N+1)]
C[0][0]=1.00
for i in range(1,N+1):
    for j in range(0,i+1):
        """
        #print(i-1)
        print(P[i-1])
        print(C[i-1][j-1])
        print(C[i-1][j-1]*P[i-1])
        """
        C[i][j]=float(C[i-1][j-1]*P[i-1])+float(C[i-1][j]*(1-P[i-1]))
        #print(C[i][j])
ans=float(0.00)
for i in range((N-1)//2+1):
    ans+=C[N][i]
ans=float(1.00-ans)
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):
    p = P[i]
    q = 1 - p
    dp[i + 1][0] = dp[i][0] * q
    for j in range(1, i + 2):
        dp[i + 1][j] = dp[i][j - 1] * p + dp[i][j] * q

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

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())
A = list(map(float,input().split()))
K = N//2  + 1
dp = [[0 for _ in range(N + 1) ] for _ in range(N + 1)]
if N == 0: 
    print(0)
    exit
dp[0][0] = 1
ans = 0
for i in range(1,N+1):
    for j in range(i+1):
        if j - 1 < 0:
            dp[i][j] = dp[i-1][j]*(1-A[i-1])
        else:
            dp[i][j] = dp[i-1][j-1]*A[i-1] + dp[i-1][j]*(1-A[i-1])
#print(dp)
for i in range(K,len(dp[N])):
        ans+=dp[N][i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())
A = list(map(float,input().split()))
K = N//2  + 1
dp = [[0 for _ in range(N + 1) ] for _ in range(N + 1)]
if N == 0: 
    print(0)
    exit
dp[0][0] = 1
ans = 0
for i in range(1,N+1):
    for j in range(i+1):
        if j - 1 < 0:
            dp[i][j] = dp[i-1][j]*(1-A[i-1])
        else:
            dp[i][j] = dp[i-1][j-1]*A[i-1] + dp[i-1][j]*(1-A[i-1])
#print(dp)
for i in range(K,len(dp[N])):
        ans+=dp[N][i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(float,input().split()))
K = N//2 + 1
import sys
sys.setrecursionlimit(10000000)

def dfs(i,K):
    if (i,K) in cache: return cache[(i,K)]
    if K < 0: 
        cache[(i,K)] = 1
        return 1
    if i>=N: 
        cache[(i,K)] = 1
        return 1
    if len(A[i:]) < K: 
        res = (1-A[i])*dfs(i+1,K)
    elif len(A[i:]) == K: 
        res = A[i]*dfs(i + 1,K-1)
    else:
        res = A[i]*dfs(i+1,K-1) + (1-A[i])*dfs(i+1,K)
    cache[(i,K)] = res
    return res
cache={}
print(dfs(0,K))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(float,input().split()))
K = N//2 + 1
import sys
sys.setrecursionlimit(10000000)


def dfs(i,K):
    if (i,K) in cache: return cache[(i,K)]
    if i>=N: 
        cache[(i,K)] = 1
        return 1
    if len(A[i:]) < K: 
        res = (1-A[i])*dfs(i+1,K)
    elif len(A[i:]) == K: 
        res = A[i]*dfs(i + 1,K-1)
    else:
        res = A[i]*dfs(i+1,K-1) + (1-A[i])*dfs(i+1,K)
    cache[(i,K)] = res
    return res
cache={}
print(dfs(0,K))

Submission status: Time Limit Exceeded

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


def solve(N: int, p: "List[float]"):
    #dp[i][j]: i枚投げて、j枚表の確率
    dp=[[0]*(N+1) for _ in range(N+1)]

    dp[0][0]=1

    # dp[1][0]=dp[0][0]*p[1]
    # dp[1][1]=dp[0][0]*(1-p[1])

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

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

    print(ans)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    p = [float(next(tokens)) for _ in range(N)]  # type: "List[float]"
    solve(N, p)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
N = int(input())
p = list(map(float, input().split()))
if N == 1:
    print(p[0])
    sys.exit()
dp = [[0 for _ in range(N + 10)] for _ in range(N + 10)]
dp[2][0] = (1.0 - p[0]) * (1.0 - p[1])
dp[2][2] = p[0] * p[1]
dp[2][1] = 1.0 - dp[2][0] - dp[2][2]
for i in range(2, N):
    for l in range(0, N + 1):
        dp[i + 1][l + 1] += dp[i][l] * p[i]
        dp[i + 1][l] += dp[i][l] * (1.0 - p[i])
ans = 0.0
for i in range(N // 2 + 1, N + 1):
    ans += dp[N][i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque
import copy
from decimal import *

N = int(input())
p = list(map(float, input().split()))
for i in range(N):
    p[i] = Decimal(str(p[i]))
if N == 1:
    print(p[0])
    sys.exit()
dp = [[Decimal("0") for _ in range(N + 10)] for _ in range(N + 10)]
dp[2][0] = (Decimal("1") - p[0]) * (Decimal("1") - p[1])
dp[2][2] = p[0] * p[1]
dp[2][1] = Decimal("1") - dp[2][0] - dp[2][2]
for i in range(3, N + 1):
    dp[i][0] = dp[i - 1][0] * p[i - 1]
for i in range(3, N + 1):
    for l in range(1, N + 1):
        dp[i][l] = dp[i - 1][l] * (Decimal("1") - p[i - 1]) + dp[i - 1][l - 1] * p[i - 1]
ans = Decimal("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(raw_input())
p = map(float, raw_input().split())

dp = np.zeros(shape=(N+1,N+1))

dp[0][0] = 1.0
dp[0][1] = 0.0

for m in range(1, N+1):
    for k in range(0, m+1):
        dp[m][k] = dp[m-1][k]*(1-p[m-1])
        if k > 0:
            dp[m][k] = dp[m][k] + dp[m-1][k-1]*p[m-1]

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

print ans

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(raw_input())
p = map(float, raw_input().split())

dp = np.zeros(shape=(N+1,N+1))

dp[0][0] = 1.0
dp[0][1] = 0.0

for m in range(1, N+1):
    for k in range(0, N+1):
        dp[m][k] = dp[m-1][k]*(1-p[m-1])
        if k > 0:
            dp[m][k] = dp[m][k] + dp[m-1][k-1]*p[m-1]

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

print ans

Submission status: Time Limit Exceeded

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

dp = [[0.0 for _ in range(n+1)] for _ in range(n+1)] #dp[i枚投げる 1はじまり][j枚表の確率 1はじまり]

dp[0][0] = 1.0 #0枚投げて0枚表の確率は1

for i in range(n): #i+1枚目を投げる 1はじまり
    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])

#print(dp)
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 itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)



        
def main(): #startline--------------------------------------------
    n = int(input())
    p = list(map(float,input().split()))
    dp = [[0]*(n+1) for i in range(n+1)]
    #dp[i][j]...i枚のコインを投げたときに表がj枚でる確率
    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)//2,n+1):
        ans += dp[n][i]
    print(ans)

if __name__ == "__main__":
    main() #endline===============================================

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
p0_list = np.array([float(item) for item in input().split()])
p1_list = 1 - p0_list

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


for i in range(N):
    dp[i+1, 0] = dp[i, 0] * p1_list[i]
    for j in range(i+1):
        dp[i+1, j+1] = dp[i, j] * p0_list[i] + dp[i, j+1] * p1_list[i]

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

Submission status: Time Limit Exceeded

Solution code:
def main():
  n=int(input())
  p=[float(i) for i in input().split()]
  
  dp=[[0]*(n+1) for i in range(n+1)]
  dp[0][0]=1
  for i in range(n):
    dp[i+1][0]=dp[i][0]*(1-p[i])
    for j in range(i+1):
      dp[i+1][j+1]=dp[i][j]*p[i]+dp[i][j+1]*(1-p[i])
  print(sum(dp[n][(n+1)//2:]))
      
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4000)

n = int(input())
p = [float(x) for x in input().split()]

dp_list = [[0]*(n+1) for i in range(n)]

def dp(i, j):
  if dp_list[i][j] == 0:
    if i == 0:
      if j == 0:
        dp_list[i][j] = 1-p[i]
      if j == 1:
        dp_list[i][j] = p[i]
    elif j-i == 1:
      dp_list[i][j] = dp(i-1, j-1)*p[i]
    elif j == 0:
       dp_list[i][j] = dp(i-1, j)*(1-p[i])
    else:
      dp_list[i][j] = dp(i-1, j)*(1-p[i]) + dp(i-1, j-1)*p[i]
  return dp_list[i][j]

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    from decimal import Decimal
    import sys
    readline = sys.stdin.readline

    n = int(readline())
    *p, = (Decimal(pi) for pi in readline().rstrip().split())

    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    # dp[投げた枚数][表の枚数] = 確率

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

    ret = sum(dp[n][j] for j in reversed(range(n + 1)) if j * 2 > n)
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

dp = [[0]*(n+1) for _ in range(n+1)]
# dp[i][j]: 最初のi枚のコインを投げたとき、表がj枚になる確率
dp[0][0] = 1.0
for i in range(n):
  for j in range(i+1):
    dp[i+1][j+1] += dp[i][j] * l[i]
    dp[i+1][j] += dp[i][j] * (1-l[i])
    
ans_ = 0
for i in range(0, n//2+1):
  ans_ += dp[n][i]
print(1-ans_)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
p_f = [0.0]
p_b = [0.0]
for p in list(map(float,input().split())):
    p_f.append(p)
    p_b.append(1.0-p)

#一次軸：コイントスの回数、二次軸：勝ち数、値：発生確率
dp = [[0.0] * (N+1) for i in range(N+1)]
dp[0][0] = 1.0

def cointoss(n_toss):
    global p_majority
    for i in range(n_toss):
        dp[n_toss][i+1] += dp[n_toss-1][i] * p_f[n_toss]
        dp[n_toss][i  ] += dp[n_toss-1][i] * p_b[n_toss]

for i in range(1,N+1):
    cointoss(i)

p_majority = 0.0
n_majority = N // 2 + 1

for i in range(n_majority,N+1):
    p_majority += dp[N][i]

print(p_majority)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(3001)

N = int(input())
p_f = [0]
p_b = [0]
for p in list(map(float,input().split())):
    p_f.append(p)
    p_b.append(1.0-p)

p_majority = 0.0
n_majority = N // 2 + 1

def cointoss(n_toss,n_front,n_back,p):
    global p_majority
    n_toss += 1
    #print(n_toss,n_front,n_back,p,p_majority,n_majority)
    if n_front+1 == n_majority:
        p_majority = p_majority + p * p_f[n_toss]
    else:
        cointoss(n_toss, n_front+1, n_back, p*p_f[n_toss])
    if n_back+1 == n_majority:
        return
    cointoss(n_toss, n_front, n_back+1, p*p_b[n_toss])

cointoss(0,0,0,1.0)
print(p_majority)

Submission status: Time Limit Exceeded

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


if __name__ == '__main__':
    main()

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

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = I()
    H = LI()
    dp = [inf]*(N)
    dp[0] = 0
    for i in range(N-1):
        dp[i+1] = min(dp[i+1],dp[i]+abs(H[i+1]-H[i]))
        if i<N-2:
            dp[i + 2] = min(dp[i + 2], dp[i]+abs(H[i + 2] - H[i]))
    ans = dp[-1]
    print(ans)
    return

def examB():
    N, K = LI()
    H = LI()
    dp = [inf]*N
    dp[0] = 0
    for i in range(N):
        for k in range(1,K+1):
            if i+k>=N:
                break
            if dp[i+k]>dp[i]+abs(H[i+k]-H[i]):
                dp[i+k] = dp[i]+abs(H[i+k]-H[i])
    ans = dp[-1]
    print(ans)
    return

def examC():
    N = I()
    A = [0]*N; B = [0]*N; C = [0]*N
    for i in range(N):
        A[i],B[i],C[i] = LI()
    dp = [[0]*3 for _ in range(N+1)]
    for i in range(N):
        dp[i+1][0] = max(dp[i][1],dp[i][2]) + A[i]
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + B[i]
        dp[i + 1][2] = max(dp[i][1], dp[i][0]) + C[i]
    ans = max(dp[N])
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    # LCS
    S = SI(); N = len(S)
    T = SI(); M = len(T)
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])

    i = N; j = M
    ans = []
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans.append(S[i-1])
            i -= 1
            j -= 1
    print("".join(ans[::-1]))
    return

def examG():
    # http://zehnpaard.hatenablog.com/entry/2018/06/26/201512
    # トポロジカルソート
    def topological_sort(n,outs,ins):
        q = deque(v1 for v1 in range(n) if ins[v1] == 0)
        res = []
        while q:
            v1 = q.popleft()
            res.append(v1)
            for v2 in outs[v1]:
                ins[v2] -= 1
                if ins[v2] == 0:
                    q.append(v2)
        return res
    N, M = LI()
    V = [[]for _ in range(N)]
    start = [0]*N
    for _ in range(M):
        x,y = LI()
        x -= 1; y -= 1
        V[x].append(y)
        start[y] += 1
    Order = topological_sort(N, V, start)
#    print(Order)
    dp = [0]*N
    for i in Order:
        for v in V[i]:
            dp[v] = max(dp[v],dp[i]+1)
    ans = max(dp)
    print(ans)
    return

def examH():
    H, W = LI()
    A = [SI() for _ in range(H)]
    dp = [[0]*W for _ in range(H)]
    dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            if A[i][j]=="#":
                continue
            dp[i][j] %=mod
            if i+1<H and dp[i+1][j]!="#":
                dp[i+1][j] +=dp[i][j]
            if j+1<W and dp[i][j+1]!="#":
                dp[i][j+1] +=dp[i][j]
    ans = dp[-1][-1]
    print(ans)
    return

def examI():
    N = I()
    P = LFI()
    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 v in dp[N][(1+N//2):]:
        ans += v
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examI()

"""

"""

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Jan 29 13:18:34 2020

@author: matsui
"""
import numpy as np


N=int(input())
P=input().split()

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

dp[1,0]=1-float(P[0])
dp[1,1]=float(P[0])

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

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 _ 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 - P[i])
    
ans = sum([dp[n][j] for j in range(n + 1) if j * 2 > n])
      
print(ans)

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

probs = [[None for _ in range(N+1)] for _ in range(N)]

probs[0][1] = Ps[0]
probs[0][0] = 1 - Ps[0]
for i in range(2, N+1):
  probs[0][i] = 0

for i in range(1, N):
  for k in range(0, N+1):
    if k == 0:
      probs[i][k] = probs[i-1][k]*(1-Ps[i])
    else:
      probs[i][k] = probs[i-1][k-1]*Ps[i] + probs[i-1][k]*(1-Ps[i])

# print(probs)

sum_all = sum(probs[N-1])
sum_ok = 0

start = int(N/2) + 1
for i in range(start, N+1):
  sum_ok += probs[N-1][i]

print(sum_ok / sum_all)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, p: "List[float]"):
    # prob[i][j]はi枚まで投げてj枚表になる確率
    prob = [[0]*(N+1) for _ in range(N+1)]
    prob[0][0] = 1
    for i in range(N):
        for j in range(N+1):
            prob[i+1][j] = prob[i][j]*(1-p[i])
            if j-1 >= 0:
                prob[i+1][j] += prob[i][j-1]*p[i]
    print(sum(prob[N][N//2+1:]))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    p = [float(next(tokens)) for _ in range(N)]  # type: "List[float]"
    solve(N, p)


if __name__ == '__main__':
    main()

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-


def main():
    n = int(input())
    p = list(map(float, input().split()))
    dp = [[0 for _ in range(n + 3)] for _ in range(n + 3)]

    # 初期化
    dp[0][0] = 1.0

    # KeyInsight
    # dp[i][j] := 最初の i 枚のコインを投げたときに、表が j 枚となる確率
    # ・状態：確率
    # ・すべての候補，条件に一致する候補をdpで管理
    # See:
    # https://qiita.com/drken/items/03c7db44ccd27820ea0d#i-%E5%95%8F%E9%A1%8C---coins
    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) // 2, n + 1):
        ans += dp[n][j]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-


def main():
    n = int(input())
    p = list(map(float, input().split()))
    dp = [[0 for _ in range(n + 100)] for _ in range(n + 100)]

    # 初期化
    dp[0][0] = 1.0

    # KeyInsight
    # dp[i][j] := 最初の i 枚のコインを投げたときに、表が j 枚となる確率
    # ・状態：確率
    # ・すべての候補，条件に一致する候補をdpで管理
    # See:
    # https://qiita.com/drken/items/03c7db44ccd27820ea0d#i-%E5%95%8F%E9%A1%8C---coins
    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) // 2, n + 1):
        ans += dp[n][j]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin,stdout

n = int(stdin.readline())
a = list( map(float,stdin.readline().split()) )

"""
state dp[i][j] -> probability of i heads among first j coins
case 1 - the current coin is Head
we need i-1 heads from j-1 coins
case 2 - the current coin is Tail
we need i heads from j-1 coins
"""
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):
    dp[0][i] = (1-a[i-1])*dp[0][i-1]
for i in range(1,n+1):
    head,tail = a[i-1],1-a[i-1]
    for n_heads in range(1,i+1):
        dp[n_heads][i] = head*dp[n_heads-1][i-1] + tail*dp[n_heads][i-1]

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

Submission status: Time Limit Exceeded

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

dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
#print(dp)

dp[0][0] = 1

for i in range(n + 1):
    for j in range(i + 1):
        if i == 0 and j == 0:
            continue
        elif j == 0:
            dp[i][j] = dp[i - 1][j] * (1 - probs[i - 1])
        else:
            dp[i][j] = dp[i - 1][j] * (1 - probs[i - 1]) + dp[i - 1][j - 1] * probs[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)]
DP[0]=10**12
for i in range(N):
    #DP[0]=1
    for j in range(N+1):
        if DP[N-j]>0:
            DP[N-j+1]+=DP[N-j]*p[i]
            DP[N-j]*=(1-p[i])
    #print(DP)
print(sum(DP[N//2+1:])/(10**12))

Submission status: Time Limit Exceeded

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

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) for i in range(N+1)]

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

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

print(ans)

Submission status: Time Limit Exceeded

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

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


if __name__ == '__main__':
    p_i()

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


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

Submission status: Time Limit Exceeded

Solution code:
import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
mod = 10**9+7
N = int(input())
p = list(map(float, input().split()))
dp = [[0]*(N+1) for _ in range(N)]
dp[0][0] = 1-p[0]
dp[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])
        else:
            dp[i][j] = dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i])
print(sum(dp[-1][(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(1,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][j]+=dp[i-1][j]*(1-p[i-1])


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

Submission status: Time Limit Exceeded

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

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