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 _ in range(N+1)]# dp[i][j]: i枚目まで投げた時, j枚表になってる確率.(i枚の選び方によって変わらん?(dp[N][:]だけみるから途中はどんな順番でもいいってこと？))
dp[0][0] = 1 # 0枚投げた時は, 0枚が表っていう事象しかあり得ない.(dp[0][0]=1で,dp[0][1:]=0)

for i in range(1, N+1):
  for j in range(0, N+1):
    if j - 1 < 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]))

if N % 2==0:
  ans = sum(dp[N][int(N/2):])
else:
  ans = sum(dp[N][int(N//2)+1:])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# python3だとTLE,pypy3だとAC

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# python3だとTLE,pypy3だとAC

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# python3だとTLE,pypy3だとAC

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# python3だとTLE,pypy3だとAC

def main():
    N = int(input())
    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(1, N+1):
        for j in range(0, N+1):
            dp[i][j] = dp[i - 1][j] * \
                (1 - p[i - 1]) + dp[i - 1][j - 1] * p[i - 1]
    print(sum(dp[N][N//2+1:]))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# python3だとTLE,pypy3だとAC

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def combinations(l, m):
    if m == 1:
        for element in l:
            yield [element]
    for i, element in enumerate(l):
        for combination in combinations(l[i + 1:], m - 1):
            combination.append(element)
            yield combination


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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
plist = list(map(float, input().split()))
dp = [0]*(n+3)
dp[0]=1
for i in range(n):
    for j in reversed(range(i+2)):
        if j == 0:
            dp[0] *= 1-plist[i]
        else:
            dp[j]=(dp[j-1]*plist[i])+(dp[j]*(1-plist[i]))
       
x = n
ans = 0
while x>= n/2:
    ans += dp[x]
    x-=1

print(ans)

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-p[0]
# dp[0][1] = p[0]

for i in range(N):
    for j in range(i+1):
        # print(f"i {i}, j {j}")
        # print(f"p[i] {p[i]}, dp[i][j] {dp[i][j]}")

        if i == 0:
            dp[i+1][j] += 1-p[i]
            dp[i+1][j+1] += p[i]
        else:
            dp[i+1][j] += (1-p[i])*dp[i][j]
            dp[i+1][j+1] += p[i]*dp[i][j]
        # print("dp", dp)

ans = 0
for i, v in enumerate(dp[-1]):
    if i > N//2:
        ans += v

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd    
n=int(input())
l=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(n+1):
        if(j==0):
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])
        else:
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])+dp[i-1][j-1]*l[i-1]
ans=0
for i in range(n//2+1,n+1):
    ans+=dp[n][i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    P=list(map(float,input().split()))
    dp=[[0]*(n+1) for _ in range(n)]#コインi(0-)までで，j枚が表
    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])
    print(sum(dp[-1][n//2+1:]))
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N = gete(int)
    # p = tuple(geta(lambda s: int(s.decode()[2:])))
    p = tuple(geta(float))

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

    for i, pi in enumerate(p, 1):
        upd = [0] * (N + 1)
        qi = 1 - pi

        upd[0] = cur[0] * qi
        for j in range(1, i + 1):
            upd[j] = cur[j - 1] * pi + cur[j] * qi
        cur = upd

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    p = tuple(map(float, input().split()))
    pr = [1 - pi for pi in p]
    # DPの二次元配列を行i1＝コインの枚数、列i2＝表がでたコインの枚数、で構築する。
    # DP[][]の初期値は0。ただし0列(表が0枚になる確率)をまず初期化する。
    # DP[i1][i2]の値は、DP[i1-1][i2] * pr + DP[i1-1][i2-1] * p
    # 「表の枚数＞裏の枚数になる確率」は、DPの最下行のX列から右の列の価の合計。
    dp = [[0.0] * (n + 1) for _ in range(n + 1)]
    # ０列目を初期化する。
    dp[0][0] = 1.0 #コイン0枚目で表が０枚の確率＝１
    for i0 in range(1, n + 1):
        dp[i0][0] = dp[i0-1][0] * pr[i0-1]

    for i1 in range(1, n + 1):
        for i2 in range(1, n + 1):
            dp[i1][i2] = dp[i1-1][i2] * pr[i1-1] + dp[i1-1][i2-1] * p[i1-1]
    r = sum(dp[n][n//2+1:])
    print(r)

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[i+1][j+1]でi枚コインを投げてj枚以上表が出る確率

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


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

    dp = np.zeros((n + 1, n + 1), dtype='float64')
    dp[0, 0] = 1.0

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


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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def Probability(p,n):
    dp = np.zeros((n+1 ,n+1)) 
    for i in range(n+1):
        for j in range(n+1):
            dp[i][j] = 0.0 
    dp[0][0] = 1.0
    
    for i in range(1,n+1):
        for j in range(i+1):
            if j==0:
                dp[i][j] = dp[i - 1][j] * (1.0 - p[i]) 
            else : 
                dp[i][j] = (dp[i - 1][j] * (1.0 - p[i]) +
                            dp[i - 1][j - 1] * p[i])  
    ans=0.0
    for i in range((n+1)//2,n+1):
        ans+=dp[n][i]
    return ans 

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

a=[0]+a 

print(Probability(a,n))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2000)
input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(float, input().split())
LIN=lambda : list(IN())
mod=1000000007

#+++++

def main():
	n = int(input())
	#b , c = IN()
	#s = input()
	al = LIN()
	#p[i][j]は、i番目までにj枚が表になっている確率をあらわす。
	p = [[0]*(n+1) for _ in range(n+1)]
	p[0][0]=1
	for i in range(1, n+1):
		for j in range(n+1):
			omote = al[i-1]
			ura = 1 - omote
			p[i][j] += p[i-1][j]*ura
			if j > 0:
				p[i][j] += p[i-1][j-1]*omote
	k = p[-1][(n+1)//2:]
	#pa(k)
	r = sum(k)
	print(r)


memo_s=[]
al=[1,1]
n=1
def cc(state, maisuu):
	nokori = n-state
	if maisuu==0:
		return 1
	if nokori < maisuu:
		return 0
	global memo_s
	k = memo_s[state][maisuu]
	if k >= 0:
		return k
	
	omote = al[state]
	ura = 1-omote
	r = cc(state+1, maisuu-1)*omote
	r += cc(state+1, maisuu)*ura
	
	memo_s[state][maisuu]=r
	return r
	
def main2():
	global n
	n = int(input())
	global memo_s
	memo_s = [[-1]*(n+1) for _ in range(n+1)]
	
	v = LIN()
	global al
	al=v[:]
	
	r = cc(0, (n+1)//2)
	print(r)
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main2()
	if ret is not None:
		print(ret)

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n = ni()
p = nfa()

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.0 - p[i])

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,l=int(input()),list(map(float,input().split()))
dp=np.full([n+1,n+1],0.0)
dp[0][0]=1.0
for i in range(1,n+1):
    for j in range(i+1):
        if j==0:
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])
        else:
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])+dp[i-1][j-1]*l[i-1]
print(sum(dp[n][(n+1)//2:]))

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
setrecursionlimit(1<<30)
def f(i,s):
    if i==n:
        return s>0
    if s+(n-i)<=0:
        return 0
    if d[i][s+n]==-1:
        d[i][s+n]=a[i]*f(i+1,s+1)+(1-a[i])*f(i+1,s-1)
    return d[i][s+n]
n=input()
a=map(float,raw_input().split())
d=[[-1]*(2*n) for _ in xrange(n)]
print f(0,0)

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
setrecursionlimit(1<<30)
def f(i,s,d):
    if i==n:
        return s>0
    if s+(n-i)<=0:
        return 0
    if (i,s) not in d:
        d[i,s]=a[i]*f(i+1,s+1,d)+(1-a[i])*f(i+1,s-1,d)
    return d[i,s]
n=input()
a=map(float,raw_input().split())
print f(0,0,{})

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

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
setrecursionlimit(1<<30)
def f(i,s,d):
    if i==n:
        return s>0
    if s+(n-i)<=0:
        return 0
    if (i,s) not in d:
        d[i,s]=a[i]*f(i+1,s+1,d)+(1-a[i])*f(i+1,s-1,d)
    return d[i,s]
n=input()
a=map(float,raw_input().split())
print f(0,0,{})

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)]
# iまで見たときに表の枚数がj枚の確率

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    P = list(map(float,input().split()))
    f = [[0]*(N + 1) for _ in range(N + 1)]
    f[0][0] = 1 - P[0]
    f[0][1] = P[0]
    for i in range(1,N):
        p = P[i]
        f[i][0] = f[i - 1][0]*(1 - p)
        for j in range(1,i + 2):
            f[i][j] += p*f[i - 1][j - 1] + (1 - p)*f[i - 1][j]
    print(sum(f[N - 1][N //2 + 1:]))
    return

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# Python3 implementation of the above approach  

  
# Function to return the probability when  
# number of heads is greater than 
# the number of tails  
def Probability(p, n) :  
  
    # Declaring the DP table  
    dp=[[0 for i in range(n+1)] for i in range(n+1)]
    for i in range(n + 1) : 
        for j in range(n + 1) : 
            dp[i][j] = 0.0
  
    # Base case  
    dp[0][0] = 1.0;  
  
    # Iterating for every coin  
    for i in range(1, n + 1) :  
  
        # j represents the numbers of heads  
        for j in range(i + 1) : 
  
            # If number of heads is equal to zero  
            # there there is only one possiblity  
            if (j == 0) : 
                dp[i][j] = dp[i - 1][j] * (1.0 - p[i]);  
            else : 
                dp[i][j] = (dp[i - 1][j] * (1.0 - p[i]) +
                            dp[i - 1][j - 1] * p[i]);  
      
    ans = 0.0;  
  
    # When the number of heads is greater than (n+1)/2  
    # it means that heads are greater than tails as  
    # no of tails + no of heads is equal to n for  
    # any permuation of heads and tails  
    for i in range((n + 1)// 2, n + 1) : 
        ans += dp[n][i];  
  
    return ans;  
  
# Driver Code  
if __name__ == "__main__" :  
      
    # 1 based indexing  
    a=int(input())
    p=[0.0 for i in range(a+1)]
    ans=list(map(float,input().split()))
    for i in range(a):
        p[i+1]=ans[i]
    
        
  
    # Number of coins  
    n = len(p) - 1;  
  
    # Function call  
    print(Probability(p, n));  
  
# This code is contributed by AnkitRai01

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


def solve():
    dp = [[0]*(i+3) for i in range(N+1)]
    dp[0][1] = 1
    for i in range(1,N+1):
        for j in range(1,i+2):
            dp[i][j] = dp[i-1][j-1]*P[i-1]+dp[i-1][j]*(1-P[i-1])
    ans = sum(dp[-1][(N+3)//2:])
    return ans
print(solve())

Submission status: Time Limit Exceeded

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


def solve():
    dp = [[0]*(N+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(1,N+1):
        dp[i][0] = dp[i-1][0]*(1-P[i-1])
    for i in range(1,N+1):
        for j in range(1,i+1):
            dp[i][j] = dp[i-1][j-1]*P[i-1]+dp[i-1][j]*(1-P[i-1])
    ans = sum(dp[-1][(N+2)//2:])
    return ans
print(solve())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy


def prob(i, values):
    result = 1
    idx = 0
    for idx, v in enumerate(values):
        i, rest = divmod(i, 2)
        if rest == 1:
            result *= v
        else:
            result *= 1 - v
        idx += 1
    return result


def solve(values, nb):
    LOG.debug((values))
    dp = [[0] * (nb + 1) for _ in range(nb // 2 + 1)]
    dp[0][0] = 1
    for j in range(1, nb + 1):
        dp[0][j] = dp[0][j - 1] * (1 - values[j - 1])
    total = dp[0][-1]
    for i in range(1, nb // 2 + 1):
        for j in range(1, nb + 1):
            dp[i][j] = (
                dp[i - 1][j - 1] * values[j - 1] + (1 - values[j - 1]) * dp[i][j - 1]
            )
        total += dp[i][-1]
    # LOG.debug(("\n" + "\n".join(map(str, dp))))
    return 1 - total


def do_job():
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    N = int(input())
    values = list(map(float, input().split()))
    # values = []
    # for _ in range(N):
    #     values.append(input().split())
    result = solve(values, N)
    # 6 digits float precision {:.6f} (6 is the default value)
    print("{:.10g}".format(result))


def configure_log():
    "Configure the log output"
    log_formatter = logging.Formatter("L%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
# from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(float, data().split())
out = sys.stdout.write
# sys.setrecursionlimit(100000)
INF = int(1e9)
mod = int(1e9) + 7

n = int(data())
P = list(mdata())
dp = [0.0] * (n // 2 + 2)
dp[1] = float(1)
for i in range(n):
    for j in range(len(dp) - 1, 0, -1):
        dp[j] = dp[j - 1] * (1 - P[i]) + dp[j] * (P[i])
print(sum(dp))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
# from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(float, data().split())
out = sys.stdout.write
# sys.setrecursionlimit(100000)
INF = int(1e9)
mod = int(1e9) + 7

n = int(data())
P = list(mdata())
dp = [0.0] * (n // 2 + 2)
dp[1] = float(1)
for i in range(n):
    for j in range(len(dp) - 1, 0, -1):
        dp[j] = dp[j - 1] * (1 - P[i]) + dp[j] * (P[i])
print(sum(dp))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(float, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(1e9)
mod=int(1e9)+7


n=int(data())
P=list(mdata())
dp=[0]*(n//2+2)
dp[1]=1
for i in range(n):
    dp1=dp[:]
    for j in range(1,len(dp)):
        k=dp[j-1]*(1-P[i])+dp[j]*(P[i])
        dp1[j]=k
    dp=dp1[:]
print(sum(dp))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy


def prob(i, values):
    result = 1
    idx = 0
    for idx, v in enumerate(values):
        i, rest = divmod(i, 2)
        if rest == 1:
            result *= v
        else:
            result *= 1 - v
        idx += 1
    return result


def solve(values, nb):
    total = 0
    LOG.debug((values))
    for i in range(pow(2, nb)):
        if bin(i).count("1") >= (nb // 2) + 1:
            total += prob(i, values)
    return total


def do_job():
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    N = int(input())
    values = list(map(float, input().split()))
    # values = []
    # for _ in range(N):
    #     values.append(input().split())
    result = solve(values, N)
    # 6 digits float precision {:.6f} (6 is the default value)
    print("{:.10g}".format(result))


def configure_log():
    "Configure the log output"
    log_formatter = logging.Formatter("L%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(float, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(1e9)
mod=int(1e9)+7


n=int(data())
P=list(mdata())
dp=[0]*(n//2+2)
dp[1]=1
for i in range(n):
    dp1=dp.copy()
    for j in range(1,len(dp)):
        k=dp[j-1]*(1-P[i])+dp[j]*(P[i])
        dp1[j]=k
    dp=dp1.copy()
print(sum(dp))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read():
    N = int(input().strip())
    P = list(map(float, input().strip().split()))
    return N, P


def solve(N, P):
    # dp[i, j]: i枚目まで投げて、表がj枚出る確率
    # dp[i, j] = dp[i-1, j-1] * p[j] + dp[i, j-1] * (1-p[j])
    # 2000x(N//2)のテーブルを作るとTLEするので、圧縮して解く
    dp = [[0 for j in range(N+1)] for i in range(2)]
    dp[0][0] = 1
    for j in range(1, N+1):
        dp[0][j] = dp[0][j-1] * (1.0 - P[j-1])
    ans = 0.0
    for i in range(1, N+1):
        b = i % 2
        for j in range(i):
            dp[b][j] = 0.0
        for j in range(i, N+1):
            dp[b][j] = dp[(b-1)%2][j-1] * P[j-1] + dp[b][j-1] * (1.0 - P[j-1])
        if i > N//2:
            ans += dp[b][-1]
    return "{:.10f}".format(ans)


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Time Limit Exceeded

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