Problem:


Score : 100 points

Problem Statement

Let N be a positive odd number.

There are N coins, numbered 1, 2, \ldots, N.
For each i (1 \leq i \leq N), when Coin i is tossed, it comes up heads with probability p_i and tails with probability 1 - p_i.

Taro has tossed all the N coins.
Find the probability of having more heads than tails.

Constraints

N is an odd number.

1 \leq N \leq 2999

p_i is a real number and has two decimal places.

0 < p_i < 1

Input

Input is given from Standard Input in the following format:

N
p_1 p_2 \ldots p_N

Output

Print the probability of having more heads than tails.
The output is considered correct when the absolute error is not greater than 10^{-9}.

Sample Input 1

3
0.30 0.60 0.80

Sample Output 1

0.612

The probability of each case where we have more heads than tails is as follows:

The probability of having (Coin 1, Coin 2, Coin 3) = (Head, Head, Head) is 0.3 × 0.6 × 0.8 = 0.144;

The probability of having (Coin 1, Coin 2, Coin 3) = (Tail, Head, Head) is 0.7 × 0.6 × 0.8 = 0.336;

The probability of having (Coin 1, Coin 2, Coin 3) = (Head, Tail, Head) is 0.3 × 0.4 × 0.8 = 0.096;

The probability of having (Coin 1, Coin 2, Coin 3) = (Head, Head, Tail) is 0.3 × 0.6 × 0.2 = 0.036.

Thus, the probability of having more heads than tails is 0.144 + 0.336 + 0.096 + 0.036 = 0.612.

Sample Input 2

1
0.50

Sample Output 2

0.5

Outputs such as 0.500, 0.500000001 and 0.499999999 are also considered correct.

Sample Input 3

5
0.42 0.01 0.42 0.99 0.42

Sample Output 3

0.3821815872



Sample input:
3
0.30 0.60 0.80


Sample output:
0.612

Submission status: Time Limit Exceeded

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

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

def solve(coin, flip_res, total_tails):
    if total_tails > N/2:
            return 0
    if coin == N-1:
        if flip_res:
            return 1 - p_ar[coin]
        else:
            return p_ar[coin]
    else:
        if flip_res:
            return (1 - p_ar[coin]) * (solve(coin + 1, 0, total_tails) + solve(coin + 1, 1, total_tails + 1)) 
        else:
            return p_ar[coin] * (solve(coin + 1, 0, total_tails) + solve(coin + 1, 1, total_tails + 1)) 

print(solve(0, 0, 0) + solve(0, 1, 1))

Submission status: Time Limit Exceeded

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

def solve(N: int, p: "List[float]"):

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

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


    return


# Generated by 1.1.4 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
input = sys.stdin.readline


def main():
    N = int(input())
    P = list(map(float, input().split()))
    dp = [[0]*(N+1) for _ in range(N+1)]  # i 枚目のコインを投げたとき j 枚が表の確率

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
"""
dp[i][j] : i番目において、(表-裏)+N=j
dp[i+1][j+1] : dp[i][j] * (表)
dp[i+1][j-1] : dp[i][j] * (裏)
"""
N = int(input())
ps = list(map(float, input().split()))

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

Submission status: Time Limit Exceeded

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = [float(x) for x in input().strip().split()]
dp = [[None for i in range(n//2+2)] for j in range(n)]
for i in range(n):
    dp[i][0] =1

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

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

print(dp[0][-1])

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs,copy
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist 小数はfloat
    return list(map(float,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

n = onem()

a = l()

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs,copy
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist 小数はfloat
    return list(map(float,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

n = onem()

a = l()

dp = [0 for i in range(n+1)]
dp[0] = 1
ans = [0 for i in range(n+1)]
for i in range(n):
    for j in range(n+1):
        ans[j] = 0
    for j in range(0,n+1):
        if j == 0:
            ans[0] = dp[0]*(1-a[i])
        elif j == n:
            ans[-1] = dp[-2]*a[i]
        else:
            ans[j] = dp[j-1]*a[i] + dp[j]*(1-a[i])
    dp = ans[:]
    

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

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs,copy
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist 小数はfloat
    return list(map(float,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

n = onem()

a = l()

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

for i in range(n):
    ans = [0 for i in range(n+1)]
    for j in range(0,n+1):
        if j == 0:
            ans[0] = dp[0]*(1-a[i])
        elif j == n:
            ans[-1] = dp[-2]*a[i]
        else:
            ans[j] = dp[j-1]*a[i] + dp[j]*(1-a[i])
    dp = copy.deepcopy(ans)
    

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

Submission status: Time Limit Exceeded

Solution code:
from math import ceil

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

dp = [[0.0 for i in range(N+1)] for j in range(N+1)]
dp[0][0] = 1.0

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

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

print(res)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

dp[0][0] = 1 - coins[0]
dp[0][1] = coins[0]

for j in range(1, N):
    for h in range(j+2):
        if h == 0:
            dp[j][h] = (1 - coins[j]) * dp[j-1][0]
        else:
            dp[j][h] = (1 - coins[j]) * dp[j-1][h] + coins[j] * dp[j-1][h-1]
     
print(sum(dp[-1][head] for head in range(N//2 + 1, N+1)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

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

dp[0][0] = 1 - coins[0]
dp[0][1] = coins[0]

for j in range(1, N):
    for h in range(N+1):
        if h == 0:
            dp[j][h] = (1 - coins[j]) * dp[j-1][0]
        else:
            dp[j][h] = (1 - coins[j]) * dp[j-1][h] + coins[j] * dp[j-1][h-1]

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

Submission status: Time Limit Exceeded

Solution code:
# At DP I
import sys
sys.setrecursionlimit(99999)

def solve(P):
    dp = {}
    n = len(P)

    def solveX(index, head):
        if index >= n:
            tail = n - head
            if head > tail:
                return 1
            return 0
        if (index, head) in dp:
            return dp[(index, head)]
        sum_ = P[index] * solveX(index + 1, head + 1)
        sum_ += (1 - P[index]) * solveX(index + 1, head)
        dp[(index, head)] = sum_
        return sum_
    return solveX(0, 0)

assert solve([0.30, 0.60, 0.80]) == 0.612
assert solve([0.42, 0.01, 0.42, 0.99, 0.42]) == 0.38218158719999995

n = int(input())
P = list(map(float, input().split()))
ans = solve(P)
print(ans)

Submission status: Time Limit Exceeded

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

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():

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

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

if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

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

dp = [0]*(n+5)

for heads in range(n+1):
    tails = n-heads
    if (heads>tails):
        dp[heads]=1


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


def solve(i, heads, tails):
    if (i==len(p)):
        if (heads>tails):
            return 1
        else:
            return 0

    if (dp[i][heads]!=-1):
        return dp[i][heads]

    dp[i][heads] = p[i]*solve(i+1, heads+1, tails)+(1-p[i])*solve(i+1, heads, tails+1)
    return dp[i][heads]

print(dp[0])

Submission status: Time Limit Exceeded

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

dp = [[0]*(n+3) for i in range(n+3)]

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

for i in range(n-1, -1, -1):
    for heads in range(n+1):
        try:
            dp[i][heads] = p[i]*dp[i+1][heads+1]+(1-p[i])*dp[i+1][heads]
        except:
            pass
            #print(i, heads)

def solve(i, heads, tails):
    if (i==len(p)):
        if (heads>tails):
            return 1
        else:
            return 0

    if (dp[i][heads]!=-1):
        return dp[i][heads]

    dp[i][heads] = p[i]*solve(i+1, heads+1, tails)+(1-p[i])*solve(i+1, heads, tails+1)
    return dp[i][heads]

print(dp[0][0])

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


#dp[i][j] = p of j heads given i throws

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

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

Submission status: Time Limit Exceeded

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

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

Solution code:
# 入力
N = int(input())
p = [float(x) for x in input().split()]

# DPテーブルを初期化
dp = [[0 for x in range(N+1)] for n in range(N+1)]
dp[0][0] = 1

# ループを回す
for i in range(N):
    for x in range(N):
        dp[i+1][x+1] += dp[i][x]*p[i]
        dp[i+1][x] += dp[i][x]*(1-p[i])

# 答えを得て出力
print(sum(dp[N][N//2+1:]))

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

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

dp = [[0.0 for _ in range(N+1)] for _ in range(N+1)]
dp[1][0] = 1 - inputs[0]
dp[1][1] = inputs[0]
for i in range(2, N+1):
    tmp_dp = [0.0 for _ in range(N+1)]
    for j in range(i+1):
        if j == 0:
            dp[i][j] = dp[i-1][j] * (1 - inputs[i-1])
        else:
            dp[i][j] = dp[i-1][j] * (1 - inputs[i-1]) + dp[i-1][j-1] * inputs[i-1]

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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


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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N = I()
p = LF()

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

memo[0][0] = 1 - P[0]
memo[0][1] = P[0]

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = list(map(float, input().split()))
memo = [[0 for j in range(N+1)] for i in range(N)]

for i in range(N):
    if i == 0:
        memo[i][0] = 1 - P[i]
    else:
        memo[i][0] = memo[i-1][0] * (1 - P[i])
    for j in range(1, i+2):
        if i == 0:
            memo[i][j] = P[i]
        else:
            memo[i][j] = memo[i-1][j-1] * P[i]
            memo[i][j] += memo[i-1][j] * (1 - P[i])
            
print(sum(memo[-1][N//2+1:]))

Submission status: Time Limit Exceeded

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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
*P, = 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(i+2):
        dp[i][j] = dp[i-1][j] * (1 - P[i]) + 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 = []
for _ in range(N+1):
    l = [0] * (N+1)
    dp.append(l)

dp[0][0] = 1

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

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

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

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

dp={i:0 for i in range(n+1)}
dp[0]=1
for i in range(n):
    for j in range(i+1,0,-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)
for i in range(len(dp)):
    j=n-i
    if(i>j):
        s+=dp[i]
print(s)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = [0]
P.extend(map(float, input().split()))

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
P=[float(i) for i in input().split()]
Ans=[[0]*(n+1) for _ in range(n+1)]
Ans[0][0]=1
for i in range(1,n+1):
  for j in range(i+1):
    if j==0:
      Ans[i][j]=Ans[i-1][j]*(1-P[i-1])
    else:
      Ans[i][j]=Ans[i-1][j]*(1-P[i-1])+Ans[i-1][j-1]*P[i-1]
ans=0
for i in range(n//2+1):
  ans+=Ans[n][i]
print(1-ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, p: "List[float]"):
    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] += p[i] * dp[i][j]
            dp[i+1][j] += (1.0 - p[i]) * dp[i][j]
    return sum(dp[-1][(N // 2 + 1):])


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]"
    result = solve(N, p)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, p: "List[float]"):
    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] += p[i] * dp[i][j]
            dp[i+1][j] += (1.0 - p[i]) * dp[i][j]
    return sum(dp[-1][(N // 2 + 1):])


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]"
    result = solve(N, p)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# atcoder 動的計画法
# I Coins

def get_inputs():
    # N コインの枚数
    # ps 各コインが表となる確率の配列(リスト)
    
    N = int(input())
    
    ps = list(map(float, input().split()))
    
    return N, ps

# 動的計画法の基づきテーブルを作成する
# dp[i][j] : i番目までのコインを投げた時に、j枚が表である確率
# 漸化式は下のようになる
# dp[i + 1][j + 1] = dp[i + 1][j + 1] + dp[i][j] * p(i + 1)
# dp[i + 1][j] = dp[i + 1][j] + dp[i][j] * (1 - p(i + 1))
#
# 0相対で考えて 0<= i < N, 0 <= j <= N  

N, ps = get_inputs()

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

dp[0][0] = 1 - ps[0]
dp[0][1] = ps[0]

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

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

Submission status: Time Limit Exceeded

Solution code:
def f(n):
    ps = list(map(float, input().split()))
    ans = 0
    for b in range(2 ** n):
        if format(b, "b").count("1") > n // 2:
            pi = 1
            for i in range(n):
                if b & 1:
                    pi *= ps[i]
                else:
                    pi *= 1 - ps[i]
                b = b >> 1
            ans += pi
    print(ans)

n = int(input())
f(n)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
ps=list(map(float,input().split()))
ans=0
for b in range(2**n):
    if format(b,"b").count("1")>n//2:
        pi=1
        for i in range(n):
            if b & 1:
                pi*=ps[i]
            else:
                pi*=1-ps[i]
            b=b>>1
        ans+=pi
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
n=int(input())
p = [float(i) for i in input().split()]

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

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

Submission status: Time Limit Exceeded

Solution code:
def Coins():
    from itertools import product
    from functools import reduce
    from operator import mul
    N = int(input())
    p = list(map(float, input().split()))
    qq = product([0, 1], repeat=N)
    ans = float(0)
    for q in qq:
        if sum(q) > N // 2:
            pq = [x * y if x * y != 0 else (1 - x) * 1 for x, y in zip(p, q)]
            ans += reduce(mul, pq)
    return ans


if __name__ == '__main__':
    ans = Coins()
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

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

dp[0][0] = 1.0

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

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