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

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

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

ans = 0
if N % 2 == 0:
    start = N // 2
else:
    start = N // 2 + 1

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

Submission status: Time Limit Exceeded

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

head_prob_table[0][1] = head_prob[0]
head_prob_table[0][0] = 1-head_prob[0]

for i in range(1, N):
    for j in range(i+2):
        prob = 0
        prob += head_prob_table[i-1][j] * (1 - head_prob[i])
        if j > 0:
            prob += head_prob_table[i-1][j-1] * head_prob[i]
        head_prob_table[i][j] = prob

print(sum(head_prob_table[N-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

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

ans = 0
for k in range(n//2+1, n+1):
  ans += DP[k][n]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n=int(input())
# k=(n*(n+1))//2
l = list(map(float,input().split()))
dp=[[False for i in range(n+1)]for j in range(n+1)]
ans=0
def recur(h,t,n):
    if n==0:
        if h>t:
            global ans
            return 1
            
        return 0
    if dp[h][t]!=False:
        return dp[h][t]
    dp[h][t] = l[n-1]*recur(h+1,t,n-1)+recur(h,t+1,n-1)*(1-l[n-1])
    return dp[h][t]
print(recur(0,0,n))

Submission status: Time Limit Exceeded

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

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


s=0
def findp(h,t,p,i):
    global s
    if(i>=len(prob)):
        if(h>t):
            s+=p
        return
    
    findp(h+1,t,p*prob[i],i+1)
    findp(h,t+1,p*(1-prob[i]),i+1)
    
findp(0,0,1,0)
print('%.9f'  %s)

Submission status: Time Limit Exceeded

Solution code:
prob = []
lim = tam = 0
dp = []
import sys
sys.setrecursionlimit(100000)

def main():
    global prob, lim, dp, tam
    tam = int(input())
    lim = tam//2 + 1
    
    prob = [float(x) for x in input().split()]
    dp = [[-1]*(tam + 1) for _ in range(tam + 1)]
    
    print(coins(0, 0))
    
def coins(n, k):
    global prob, lim, dp, tam
    
    if n == tam:
        if k >= lim:
            return 1
        else:
            return 0

    if dp[n][k] != -1:
        return dp[n][k]
    
    dp[n][k] = coins(n + 1, k)*(1 - prob[n-1]) + coins(n + 1, k + 1)*prob[n-1]
    return dp[n][k]
     
main()

Submission status: Time Limit Exceeded

Solution code:
import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
sys.setrecursionlimit(200000000)
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
#def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])

    
def fun(A,N,h,t,dp):
    if N < 0:
        return 0
    if N==0:
        if h > t:
            return 1
        return 0
    x = dp.get((N,h,t),-1)
    if x!= -1:
        return x
    else:
        dp[(N,h,t)] = A[N-1]*fun(A,N-1,h+1,t,dp) + (1 - A[N-1])*fun(A,N-1,h,t+1,dp)
        return dp[(N,h,t)]
        
N = int(input())
A = list(map(float, input().split()))
dp = {}
print(fun(A,N,0,0,dp))

Submission status: Time Limit Exceeded

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


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

ans = 0
for omote in range(N+1):
    ans += dp[N][omote] if omote > N - omote else 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    naf = lambda: list(map(float, sys.stdin.readline().split()))

    n = ni()
    p = naf()

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

    # dp[i][j] : pのうちi個めまでを投げて、表がj個出る確率
    for i in range(n):
        for j in range(n):
            dp[i + 1][j + 1] += dp[i][j] * p[i]
            dp[i + 1][j] += dp[i][j] * (1 - p[i])

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


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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
prob = []
lim = 0

import sys
sys.setrecursionlimit(100000)

def main():
    global prob, lim
    n = int(input())
    lim = n//2 + 1

    prob = [float(x) for x in input().split()]

    print(coins(n, 1, 0))
    
def coins(n, p, k):
    global prob, lim
    
    if k == lim:
        return p
    if n == 0 or k + n < lim:
        return 0
    
    return coins(n - 1, p*(1 - prob[n-1]), k) + coins(n - 1, p*prob[n-1], k + 1) 

main()

Submission status: Time Limit Exceeded

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_i
import math
N = int(input())
P_List = list(map(float,input().split()))
dp = [[0 for j in range(N + 1)] for i in range(N+1)]
std = math.ceil(N/2)
for i in range(N+1):
    if i == 0:
        dp[i][0] = 1
    else:
        Current_P = P_List[i - 1]
        for j in range(i + 1):
            if (N - i + j) < std:
                dp[i][j] = 0
            elif j == 0:
                dp[i][j] = dp[i - 1][j]*(1 - Current_P)
            elif j != i:
                dp[i][j] = (dp[i - 1][j]*(1 - Current_P)) + (dp[i - 1][j - 1]*Current_P)
            else:
                dp[i][j] = dp[i - 1][j - 1]*Current_P
    
print(sum(dp[N][math.ceil(std):]))

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

Submission status: Time Limit Exceeded

Solution code:
prob = []
const = 0
import sys
sys.setrecursionlimit(100000)

def main():
    global prob, const

    n = int(input())
    const = n//2 + 1

    prob = [float(x) for x in input().split()]

    print(coins(n, 1, 0))
    
def coins(n, p, k):
    global prob, const
    
    if k == const:
        return p
    if n == 0:
        return 0
    
    return coins(n - 1, p*(1 - prob[n-1]), k) + coins(n - 1, p*prob[n-1], k + 1) 

main()

Submission status: Time Limit Exceeded

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_i
import math
N = int(input())
P_List = list(map(float,input().split()))
dp = [[] * N for i in range(N+1)]
std = math.ceil(N/2)
for i in range(N+1):
    if i == 0:
        dp[0].append(1)
    else:
        Current_P = P_List[i - 1]
        for j in range(i + 1):
            if (N - i + j) < std:
                dp[i].append(0)
            elif j == 0:
                dp[i].append(round(dp[i - 1][j]*(1 - Current_P),10))
            elif j != i:
                dp[i].append(round((dp[i - 1][j]*(1 - Current_P)) + (dp[i - 1][j - 1]*Current_P),10))
            else:
                dp[i].append(round(dp[i - 1][j - 1]*Current_P,10))
    
print(sum(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal
n=int(input())
p=list(map(Decimal,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[j][i+1]+=dp[j][i]*(1-p[i])
        dp[j+1][i+1]+=dp[j][i]*p[i]

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

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
P_List = list(map(float,input().split()))
dp = [[] * N for i in range(N+1)]

for i in range(N+1):
    if i == 0:
        dp[0].append(1)
    else:
        Current_P = P_List[i - 1]
        for j in range(i + 1):
            if j == 0:
                dp[i].append(round(dp[i - 1][j]*(1 - Current_P),10))
            elif j != i:
                dp[i].append(round((dp[i - 1][j]*(1 - Current_P)) + (dp[i - 1][j - 1]*Current_P),10))
            else:
                dp[i].append(round(dp[i - 1][j - 1]*Current_P,10))
    
print(sum(dp[N][math.ceil(N/2):]))

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
P_List = list(map(float,input().split()))
dp = []
for i in range(N):
    Current_List = [1-P_List[i],P_List[i]]
    if i == 0:
        dp.append(Current_List)
    else:
        dp.append([x*y for x in dp[i-1] for y in Current_List])

Standard = math.ceil(N/2)
Ans = 0
for k in range(len(dp[-1])):
    if bin(k).count("1") >= Standard:
       Ans += dp[-1][k]

print(round(Ans,10))

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
P_List = list(map(float,input().split()))
dp = []
for i in range(N):
    Current_Fault_P,Current_Correct_P = 1-P_List[i],P_List[i]
    if i == 0:
        dp.append([Current_Fault_P,Current_Correct_P])
    else:
        dp.append([])
        for j in dp[i-1]:
            dp[i].append(round(j*Current_Fault_P,10))
            dp[i].append(round(j*Current_Correct_P,10))

Standard = math.ceil(N/2)
Ans = 0
for k in range(len(dp[-1])):
    if bin(k).count("1") >= Standard:
       Ans += dp[-1][k]

print(round(Ans,10))

Submission status: Time Limit Exceeded

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

# dp[i][j] = i個目までのコインで、表の個数がj個である確率
# dp[i][j] = dp[i - 1][j] * (1 - P[i]) + dp[i - 1][j - 1] * P[i]
# dp[0][0] = 1 # 0個目までのコインで、表の個数が0個である確率は1

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
x=50000
sys.setrecursionlimit(x)

n=int(input())
arr = list(map(float,input().split()))
dp = [[-1]*(3001) for i in range(3001)]

def func(n,x):
    if x==0:
        return 1
    if dp[n][x]>-0.9:
        return dp[n][x]  
    if n==0:
        return 0
    
    dp[n][x] = (arr[n-1])*func(n-1,x-1) + (1-arr[n-1])*func(n-1,x)
    return dp[n][x]

print("%0.10f"%func(n,(n+1)//2))

Submission status: Time Limit Exceeded

Solution code:

n=int(input())
arr = list(map(float,input().split()))
dp = [[-1]*(n+1) for i in range(n+1)]


def func(n,x):
    for i in range(0,n+1):
        for j in range(0,n+1):
            if j==0:
                dp[i][j] = 1
            elif i==0:
                dp[i][j]=0
            else:
                p=(arr[i-1])*dp[i-1][j-1]
                q=(1-arr[i-1])*dp[i-1][j]
                dp[i][j] = p+q 
    
    return dp[n][x]

print("%0.10f"%func(n,(n+1)//2))

Submission status: Time Limit Exceeded

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

import sys
x=5000
sys.setrecursionlimit(x)
def func(n,x):
    if x==0:
        return 1
    if dp[n][x]>-0.9:
        return dp[n][x]  
    if n==0:
        return 0
    
    dp[n][x] = (arr[n-1])*func(n-1,x-1) + (1-arr[n-1])*func(n-1,x)
    return dp[n][x]

print("%0.10f"%func(n,(n+1)//2))

Submission status: Time Limit Exceeded

Solution code:
import sys
x=50000
sys.setrecursionlimit(x)

n=int(input())
arr = list(map(float,input().split()))
dp = [[-1]*(3001) for i in range(3001)]

def func(n,x):
    if x==0:
        return 1
    if dp[n][x]>-0.9:
        return dp[n][x]  
    if n==0:
        return 0
    
    dp[n][x] = (arr[n-1])*func(n-1,x-1) + (1-arr[n-1])*func(n-1,x)
    return dp[n][x]

print("%0.10f"%func(n,(n+1)//2))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

print(sum_)

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(i+1):
        prob = dp[i-1][j-1]*p[i-1]
        if i > 0:
            prob += dp[i-1][j]*(1.-p[i-1])
        dp[i][j] = max(dp[i][j], prob)
print(sum(dp[-1][N//2+1:]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


def debug(*x):
    print(*x)


def solve(N, probs):
    "void()"
    m = [0.0] * (N + 1)
    m[0] = 1.0

    for i in range(N):
        n = [0.0] * (N + 1)
        for j in range(N):
            n[j + 1] += m[j] * probs[i]
        for j in range(N + 1):
            n[j] += m[j] * (1 - probs[i])
        m = n
    return sum(m[N // 2 + 1:])


def main():
    N = int(input())
    probs = list(map(float, input().split()))
    print(solve(N, probs))


T1 = """
3
0.30 0.60 0.80
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    0.612
    """


T3 = """
5
0.42 0.01 0.42 0.99 0.42
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    0.3821815872
    """


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import math

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

dp = [[0] * (n+1) for _ in range(n+1)] #行は表の枚数、列は試行回数
dp[0][0] = 1
for i in range(0, n):
    for j in range(0, n):
        dp[i+1][j+1] += dp[i][j] * lst[i] #表のとき
        dp[i+1][j] += dp[i][j] * (1 - lst[i]) #裏のとき
        
hlf = math.ceil(n/2)
ansl = dp[n][hlf:n+1]
ans = sum(ansl)
print(ans)

Submission status: Time Limit Exceeded

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

dp = np.array([[0.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] * arr[i]
        dp[i + 1, j] += dp[i, j] * (1 - arr[i])

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

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

Submission status: Time Limit Exceeded

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

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

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


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

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.00-p[i])
ans = 1.00
for i in range(int((n+1)/2)):
    ans -= dp[n][i]
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=[int(x[2:]) for x 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(i+1):
    dp[i][j]=dp[i-1][j]*(100-p[i-1])
    if j > 0:
      dp[i][j]+=dp[i-1][j-1]*p[i-1]
res = 0
for j in range((n+1)//2,n+1):
  res += dp[n][j]
print(res / 100**n)

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal

N = int(input())
p = [i for i in map(Decimal, input().split(" "))]

dp = [[Decimal(0)] * (N+1) for _ in range(N+1)]
dp[0][0] = Decimal(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] * (Decimal(1.0)-p[i])

res = Decimal(0.0)
for i in range(N//2+1, N+1):
    res += dp[N][i]
print("{:.10f}".format(res))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal

n = int(input())
p = list(input().split())

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

dp[0][0] = 1

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

num = 0

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

print(num)

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

Submission status: Time Limit Exceeded

Solution code:

n=int(input())

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

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

dp[0][0]=1.0

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

res=0.0

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


print(res);

Submission status: Time Limit Exceeded

Solution code:

n=int(input())

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

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

dp[0][0]=1.0;

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

res=0.0

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


print(res);

Submission status: Time Limit Exceeded

Solution code:

n=int(input())

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

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

dp[0][0]=1.0;

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

res=0.0

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


print(res);

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
buf = sys.stdin.buffer

N = int(buf.readline())
M = N // 2 + 1
P = np.array(buf.readline().split(),dtype = float)
#print(P)
dp = np.zeros([N + 1,N + 1])
dp[0][0] = 1.0

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

print(sum(dp[-1][M:]))

Submission status: Time Limit Exceeded

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

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

print(sum(dp[-1][M:]))

Submission status: Time Limit Exceeded

Solution code:


def coin(n,arr):

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






n=int(input())
arr=list(map(float,input().split()))
# res=independent_set(n,graph)

res=coin(n,arr)

# res=ways(100,10**5,[randint(0,10**5) for _ in range(100)])
print(res)

Submission status: Time Limit Exceeded

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

dp = defaultdict(float)
dp[(0, 0)] = 1.0

for p in P:
    newDP = defaultdict(float)
    for (X, Y), val in dp.items():
        # 表が出る
        newDP[(X + 1, Y)] += val * p
        # 裏が出る
        newDP[(X, Y + 1)] += val * (1 - p)
    dp = newDP

ans = 0.0
for x in range(N + 1):
    y = N - x
    if x > y:
        ans += dp[(x, y)]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    assert N % 2 == 1
    M = (N + 1) // 2
    P = list(map(float, input().split(' ')))
    dp = [[0 for _ in range(M + 1)] for _ in range(N)]
    dp[0][0] = 1 - P[0]
    dp[0][1] = P[0]
    for n in range(1, N):
        p = P[n]
        for m in range(M + 1):
            if m == M:
                dp[n][m] = dp[n - 1][m] + dp[n - 1][m - 1] * p
            elif m >= 1:
                dp[n][m] = dp[n - 1][m] * (1 - p) + dp[n - 1][m - 1] * p
            else:
                # m == 0
                dp[n][m] = dp[n - 1][m] * (1 - p)
    print(dp[-1][-1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)


@lru_cache(maxsize=None)
def rec(i, j):
    if i < 0 or j < 0:
        return 0.0
    if i == 0 and j == 0:
        return 1.0
    global p
    return rec(i - 1, j) * (1 - p[i - 1]) + rec(i - 1, j - 1) * p[i - 1]


def main():
    N = int(input())
    global p
    p = list(map(float, input().split()))
    ans = 0
    for i in range(N + 1):
        for j in range(N+1):
            ret = rec(N, i)
            if j == N and i > N // 2:
                ans += ret
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)


@lru_cache(maxsize=None)
def rec(i, j):
    global p
    if i < 0 or j < 0:
        return 0.0
    if i == 0 and j == 0:
        return 1.0
    return rec(i - 1, j) * (1 - p[i - 1]) + rec(i - 1, j - 1) * p[i - 1]


def main():
    N = int(input())
    global p
    p = list(map(float, input().split()))
    ans = 0
    for i in range(N // 2 + 1, N + 1):
        ans += rec(N, i)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# python3だとTLE,pypy3だとAC
import sys
sys.setrecursionlimit(10**6)


def get(i, j):
    global dp
    global p
    if i < 0 or j < 0:
        return 0.0
    if dp[i][j] == 0.0:
        dp[i][j] = get(i - 1, j) * (1 - p[i - 1]) + \
            get(i - 1, j - 1) * p[i - 1]
    return dp[i][j]


def main():
    N = int(input())
    global dp
    global p
    p = list(map(float, input().split()))
    dp = [[0.0] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 1.0
    for i in range(N, 0, -1):
        get(N, i)
    print(sum(dp[N][N//2+1:]))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

# コインをi枚使い、表がj枚である確率
dp = [[0]*(N+1) for _ in range(N+1)]
dp[0][0] = 1

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

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

Submission status: Time Limit Exceeded

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

def f(i, x, dp, p):

    if x == 0:
        return 1
    if i == 0:
        return 0

    if dp[i][x] > -0.9:
        return dp[i][x]

    dp[i][x] = f(i - 1, x, dp, p) * (1 - p[i - 1]) + f(i - 1, x - 1, dp, p) * (p[i - 1])
    return dp[i][x]

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

dp = [[-1 for i in range(n + 1)] for j in range(n + 1)]
x = ((n + 1)//2)
print(f(n, x, dp, arr))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

def f(p, n, t, h, dp):

    if n == 0:
        if h > t:
            return 1

        return 0

    if (t, h) in dp:
        return dp[(t, h)]

    dp[(t, h)] = f(p, n - 1, t+1, h, dp) * (1 - p[n - 1]) + f(p, n - 1, t, h+1, dp) * (p[n - 1])
    return dp[(t, h)]

n = int(input())
arr = list(map(float, input().split()))
dp = {}

print(f(arr, n, 0, 0, dp))

Submission status: Time Limit Exceeded

Solution code:
# cook your dish here
from itertools import permutations 
n = int(input())
arr = list(map(float, input().split()))
res1 = [[]]
c = 1
while(c != n//2+1):
    r = []
    for i in range(1,n-c+1):
        r.append(0)
    for i in range(n-c, n):
        r.append(1)
    c += 1
    res1.append(r)

res1 = res1[1:]

res2 = [[]]
for i in res1:
    l = list(permutations(i))
    for j in l:
        res2.append(j)
    
res2 = res2[1:]

res3 = [[]]
for i in res2:
    if(i not in res3):
        res3.append(i)

res3 = res3[1:]

b = 1.0
result = 0.0
for i in range(n):
    b = float(b)*float(arr[i])
    result = float(b)

for i in res3:
    b = 1.0
    for j in range(len(i)):
        if(i[j] == 0):
            b = float(b)*float(arr[j])
        else:
            b = float(b)*float(1-arr[j])
    #print(b)
    result += float(b)
    
print(result)