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: Accepted

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

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

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

Submission status: Accepted

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 head in range(N):
        dp[i+1][head+1] += dp[i][head] * P[i]
        dp[i+1][head] += dp[i][head] * (1-P[i])

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

Submission status: Accepted

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

dp = [[0 for j in range(N+1)] for i in range(N)]#i+1枚目までのコインを投げたときにj枚表が出る確率

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

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

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

Submission status: Accepted

Solution code:
def main():
    n=int(input()) 
    p = input().split()
    for i in range(n):
        p[i]=float(p[i])    
    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(n+1):
            dp[i][j]=dp[i-1][j-1]*p[i-1]+dp[i-1][j]*(1-p[i-1])
        
    ans=0
    for i in range((n+1)//2):
        ans+=dp[n][-i-1]
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    pl = tuple(map(float, input().split()))
    mid = (N + 1) // 2
    v = [0.0] * (mid + 1)
    v[0] = 1.0
    for i, p in enumerate(pl[:mid]):
        q = 1 - p
        t = 0.0
        for j, uu in enumerate(v[:i + 2]):
            v[j] = t * p + uu * q
            t = uu
    for i, p in enumerate(pl[mid:], mid):
        q = 1 - p
        t = v[i - mid + 1]
        for j, uu in enumerate(v[i - mid + 2:mid], i - mid + 2):
            v[j] = t * p + uu * q
            t = uu
        v[mid] += t * p
    print(v[mid])

main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    pl = tuple(map(float, input().split()))
    v = [1 - pl[0], pl[0]]
    mid = (N + 1) // 2
    for i, p in enumerate(pl[1:mid], 1):
        v = v + [0.0]
        t = v[0]
        v[0] = t * (1 - p)
        for j, uu in enumerate(v[1:], 1):
            v[j] = t * p + uu * (1 - p)
            t = uu
    for i, p in enumerate(pl[mid:], mid):
        t = v[i - mid + 1]
        for j, uu in enumerate(v[i - mid + 2:-1], i - mid + 2):
            v[j] = t * p + uu * (1 - p)
            t = uu
        v[mid] += t * p
    print(v[mid])

main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    pl = list(map(float, input().split()))
    v = [1 - pl[0], pl[0]]
    mid = (N + 1) // 2
    for i, p in enumerate(pl[1:mid], 1):
        v = v + [0.0]
        t = v[0]
        v[0] = t * (1 - p)
        for j, uu in enumerate(v[1:], 1):
            v[j] = t * p + uu * (1 - p)
            t = uu
    for i, p in enumerate(pl[mid:], mid):
        t = v[i - mid + 1]
        for j, uu in enumerate(v[i - mid + 2:-1], i - mid + 2):
            v[j] = t * p + uu * (1 - p)
            t = uu
        v[mid] += t * p
    print(v[mid])

main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    p = list(map(float, input().split()))
    u = [0.0]
    v = [1 - p[0], p[0]]
    for i, p in enumerate(p[1:], 1):
        u, v = v, u + [0.0, 0.0]
        t = u[0]
        v[0] = t * (1 - p)
        for j, uu in enumerate(u[1:], 1):
            v[j] = t * p + uu * (1 - p)
            t = uu
        v[-1] = t * p
    print(sum(v[(N + 1) // 2:]))

main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

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

"""
・表が出た枚数 -> 確率でdp遷移
・多項式((1-p)+px)をかけていく
"""

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

for p in P:
    prev = dp
    dp = prev * (1-p)
    dp[1:] += prev[:-1] * p

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = float("inf")


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

    dp = [[0]*(N+1) for _ in range(N+1)]
    dp[0][0] = 1.0
    for i in range(N):
        for j in range(i+1):
            dp[i+1][j+1] += dp[i][j] * P[i]
            dp[i+1][j] += dp[i][j] * (1 - P[i])
    
    ans = 0.0
    for n in range((N+1)//2, N+1):
        ans += dp[N][n]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

dp = [[0]*(N+1) for _ in range(N+1)]
#dp[i][j]:i枚コインを投げた時、j枚表が出る確率

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

Submission status: Accepted

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

        if i <= 2*j and i == n:
            ans += dp[i][j]


print(ans)

Submission status: Accepted

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

        if i <= 2*j and i == n:
            ans += dp[i][j]


print(ans)

Submission status: Accepted

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

ans = 0

DP = []
for _ in range(3000):
    DP.append([0] * 3000)
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]

ans = 0
i = N
while i > N//2:
    ans += DP[N][i]
    i -= 1

print(ans)

Submission status: Accepted

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

DP = [[0.0] * (N+1) for i in range(N+1)]

DP[0][0] = 1.0 - p[0]
DP[0][1] = p[0]

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

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

print(Sum)

Submission status: Accepted

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

#dp[i][j]:コインiまでで表がj枚でる確率
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
dp[1][1] = P[0]
dp[1][0] = 1 - P[0]
for i in range(2,N+1):
  for j in range(i+1):
    if j == 0:
      dp[i][j] = dp[i-1][0] * (1-P[i-1])
    elif j == i:
      dp[i][j] = dp[i-1][j-1] * P[i-1]
    else:
      dp[i][j] = dp[i-1][j] * (1-P[i-1]) + dp[i-1][j-1] * P[i-1]

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

Submission status: Accepted

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

Submission status: Accepted

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

"""
Recursive top down

# def solve(i,k):
#     # print(i,k)
#     if i<=n-1 and k>0 and dp[i][k]:
#         return dp[i][k]
#     if k<=0:
#         # if i not in dp:
#         #     dp[i] ={}
#         # dp[i][k] = 1
#         return 1

#     elif i>n-1:
#         # if i not in dp:
#         #     dp[i] ={}
#         # dp[i][k] = 0
#         return 0
#     elif k>n-i:
#         # if i not in dp:
#         #     dp[i] ={}
#         dp[i][k] = 0

#     else:
#         # if i not in dp:
#         #     dp[i] ={}
#         dp[i][k] = p[i]*solve(i+1,k-1)+(1-p[i])*solve(i+1,k)
#     return dp[i][k]


# print(solve(0,n//2+1))


"""

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(float,sys.stdin.readline().split()))

n = I()
P = LI()
dp = [[0]*(n+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
    p = P[i-1]
    for j in range(n+1):
        if j > 0:
            dp[i][j] = (1-p)*dp[i-1][j] + p*dp[i-1][j-1]
        else:
            dp[i][j] = (1-p)*dp[i-1][j]
print(sum(dp[-1][n//2+1:]))

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function
from collections import defaultdict, Counter, deque
from future_builtins import ascii, filter, hex, map, oct, zip
from itertools import imap as map, izip as zip
from itertools import permutations
from __builtin__ import xrange as range
from math import ceil
from _continuation import continulet
from cStringIO import StringIO
from io import IOBase
import __pypy__
from math import log, ceil, floor
from bisect import bisect, insort, bisect_left, bisect_right
from heapq import heapify, heappop, heappush
import sys
import os
import re
inf = float('inf')
mod = int(1e9) + 7
mod_ = 998244353
 
'''

!!!!!!!!!!!!!!!!!!!!!!!!   WAIT FFS    !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
DONOT SUBMIT RECKLESSLY
One wrong submission = 10 mins penalty!
Check for special cases (n=1)

'''

def printGrid(grid):
	for row in grid:
		print(' '.join(list(map(str, row))))


def main():
	n = int(input())
	prob = [0] + list(map(float, input().split()))
	dp = [[0]*(n+1) for i in range(n+1)]
	# dp[i][j] = prob of getting j heads with i coin tosses
	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] * prob[i] if j-1 >= 0 else 0) + dp[i-1][j] * (1 - prob[i])
			
	total = 0
	for i in range((n+1)//2, n+1):
		total += dp[n][i]

	# printGrid(dp)
	print(total)



# Fast IO
BUFSIZE = 8192
class FastI(IOBase):
	def __init__(self, file):
		self._fd = file.fileno()
		self._buffer = StringIO()
		self.newlines = 0
 
	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
		self.newlines = 0
		return self.buffer.read()
 
	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count("\n") + (not b)
			ptr = self._buffer.tell()
			self._buffer.seek(0, 2), self._buffer.write(
				b), self._buffer.seek(ptr)
		self.newlines -= 1
		return self._buffer.readline()
class FastO(IOBase):
	def __init__(self, file):
		self._fd = file.fileno()
		self._buffer = __pypy__.builders.StringBuilder()
		self.write = lambda s: self._buffer.append(s)
 
	def flush(self):
		os.write(self._fd, self._buffer.build())
		self._buffer = __pypy__.builders.StringBuilder()
def print(*args, **kwargs):
	sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop("end", "\n"))
	if kwargs.pop("flush", False):
		file.flush()
def gcd(x, y):
	while y:
		x, y = y, x % y
	return x
sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
def input(): return sys.stdin.readline().rstrip("\r\n")
if __name__ == "__main__":
	def bootstrap(cont):
		call, arg = cont.switch()
		while True:
			call, arg = cont.switch(to=continulet(
				lambda _, f, args: f(*args), call, arg))
	cont = continulet(bootstrap)
	cont.switch()
	main()

Submission status: Accepted

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

head = np.zeros(n+1)
head[0] = 1
for i in range(n):
  #print(head)
  mask = np.r_[np.ones(i+1), np.zeros(n-i)]
  h1 = head * (1 - p[i]) * mask
  h2 = head * p[i] * mask
  head = h1 + np.r_[np.zeros(1), h2[:-1]]

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

Submission status: Accepted

Solution code:
N = int(input())
dp = [0] * (N+1)
dp[0] = 1
ans = 0

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

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

        if j > N // 2:
            ans += dp[j]
            dp[j] = 0
            break

print(ans)

Submission status: Accepted

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

dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1
# dp[投][裏]

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

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

Submission status: Accepted

Solution code:
n = int(input())

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

dp = [[0]*(n+1) for _ in range(n)]
#０が裏、1が表
#dp[枚数][表の枚数]
dp[0][0] = 1-p[0]
dp[0][1] = p[0]

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

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
def LILI(n): return [LI() for _ in range(n)]
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N = II()
    p = LF()

    # dp[これまでに表が出た数][コインの番号], 中身は確率
    dp = [[0.0 for _ in range(N+1)] for _ in range(N)]
    dp[0][0] = 1 - p[0]
    dp[0][1] = p[0]

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

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

    print(ans)

main()

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys

#TODO: Find a better DP solution
#Current is just a recursive solution
#Time complexity of recursive solutions?

class Solution(object):
	def __init__(self):
		self.n = 0
		self.p = []
		self.result = 0

	def readInput(self):
		self.n = int(sys.stdin.readline())
		a = sys.stdin.readline().split()
		for i in xrange(self.n):
			self.p.append(float(a[i]))
		#print self.p

	def coinTossRec(self, idx, tail_count, prob):
		if idx == self.n - 1:
			#last index
			self.result += (prob * self.p[idx])
			if tail_count != 0:
				#Check for head
				self.result += (prob * (1-self.p[idx]))
		else:
			self.coinTossRec(idx+1, tail_count, prob * self.p[idx])
			if tail_count != 0:
				self.coinTossRec(idx+1, tail_count-1, prob * (1-self.p[idx]))

	def coinTossIter(self):
		dp = [0] * (self.n + 1) #i is the probability of i heads so far
		dp[0] = 1
		for i in xrange(self.n):
			p_heads = self.p[i]
			for j in xrange(i+1, -1, -1):
				if j == 0:
					dp[j] = dp[j] * (1 - p_heads)
				else:
					dp[j] = dp[j-1] * p_heads + dp[j] * (1- p_heads)
		ans = 0
		for i in xrange((self.n//2) + 1, self.n+1):
			ans += dp[i]

		print ans

	def coinToss(self):
		tail_count = self.n // 2 if self.n %2 == 1 else self.n //2 - 1
		self.coinTossRec(0, tail_count, 1)
		print self. result		


if __name__ == '__main__':
	s = Solution()
	s.readInput()
	s.coinTossIter()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
p=[float(x) for x in input().split()]
dp=[[0 for j in range(N+5)] for i in range(N+5)]
dp[0][0]=1
for i in range(N):
    for j in range(i+1):
        dp[i+1][j+1] += dp[i][j]*p[i]
        dp[i+1][j] += dp[i][j]*(1-p[i])
M =(N+1)//2
result = 0
for i in range(M,N+1):
    result += dp[N][i]
print(result)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
from copy import *

N = int(input())
p = list(map(float, input().split()))
dp = [[0] * (N+1) for i in range(N+1)]
dp[0][0] = 1
for i in range(N):
    for j in range(i+2):
        if j != 0:
            dp[i+1][j] += dp[i][j-1]*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: Accepted

Solution code:
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

def sol():
    N = int(input())
    prob = map(float, input().split())

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

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

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


sol()

Submission status: Accepted

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

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

prob = 0

for i in range(N // 2 + 1):
    prob += A[N][i]

print(1 - prob)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

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

dp = np.zeros(N+1) # 表の回数ごとの確率
dp[0] = 1.0
for p in P:
    prev = dp.copy()
    dp *= (1-p)
    dp[1:] += p * prev[:-1]

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