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

Solution (Python):
import sys,collections as cl,bisect as bs,copy
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(float,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    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): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    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:]))

Solution (Python):



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

Solution (Python):

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

	
	print(total)




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

Solution (Python):
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):
  
  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:]))

Solution (Python):
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)

Solution (Python):
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)

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

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


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)

Solution (Python):
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)))

Solution (Python):
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 d in range(i+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)

Solution (Python):
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 = [[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()

Solution (Python):
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:]))

Solution (Python):
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()

Solution (Python):
import sys





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

	def coinTossRec(self, idx, tail_count, prob):
		if idx == self.n - 1:
			
			self.result += (prob * self.p[idx])
			if tail_count != 0:
				
				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) 
		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()

Solution (Python):
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())

Solution (Python):
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:]))

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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[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()

Solution (Python):
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)

Solution (Python):
import decimal,math

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)

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

Solution (Python):

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


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

Solution (Python):
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:]))

Solution (Python):
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)