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
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis=list(map(float,input().rstrip().split(" ")))
dp=[[0]*(n+1) for i in range(n+1)]
dp[0][0]=1
for i in range(n):
    for j in range(n):
        dp[i+1][0]=dp[i][0]*(1-lis[i])
        dp[i+1][j+1]=dp[i][j]*lis[i]+dp[i][j+1]*(1-lis[i])

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

Solution (Python):


INF = float('inf')


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

    
    
    
    
    
    
    
    

    
    

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

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


tc()

Solution (Python):


INF = float('inf')


def tc():
    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):
        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 = sum(dp[n][n // 2 + 1:])
    print(ans)


tc()

Solution (Python):
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):
        p = P[i]
        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:]))

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




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

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

Solution (Python):
import sys
from copy import copy

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(float, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N = in_n()
    p = in_nl()

    dp = [0] * (N + 1)
    dp[0] = 1 - p[0]
    dp[1] = p[0]

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

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


if __name__ == '__main__':
    main()

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

dp = [1] * (n + 1)
dp2 = [1] * (n + 1)
dp[0] = 1 - p[0]
dp[1] = p[0]

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

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

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def FI(): return list(map(float, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


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


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

Solution (Python):

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

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

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

print(p)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





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

Solution (Python):
n = int(input())
probs = [float(i) for i in input().split()]
dp = [[0]*n for i in range(n)]
for i in range(n):
    if i==n//2:
        dp[n-1][i] = probs[n-1]
    elif i<n//2:
        dp[n-1][i] = 0 
    else:
        dp[n-1][i] = 1
for i in range(n-2, -1,-1):
    for j in range(i, -1,-1):
        dp[i][j] = probs[i] * dp[i+1][j+1] + (1-probs[i])*dp[i+1][j] 
print(dp[0][0])

Solution (Python):
import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate

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

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):
    dp = list2d(3000,3000,0)
    dp[0][0] = 1 - A[0]
    dp[0][1] = A[0]
    for i in range(1,N):
        for j in range(3000):
            
            dp[i][j] += (1-A[i])*dp[i-1][j]
            
            if j > 0:
                dp[i][j] += A[i]*(dp[i-1][j-1])
    ans = 0
    for i in range(N//2 + 1,3000):
        ans += dp[N-1][i]
    return ans
        
N = int(input())
A = list(map(float, input().split()))
print(fun(A,N))

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)


N = int(input())
p = [0] + list(map(float, input().split()))

m = N // 2 + 1

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

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

print(dp[N][m])

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

Solution (Python):




from sys import stdin, stdout, setrecursionlimit
from math import gcd, ceil, sqrt
from collections import Counter
from bisect import bisect_left, bisect_right
ii1 = lambda: int(stdin.readline().strip())
is1 = lambda: stdin.readline().strip()
iia = lambda: list(map(int, stdin.readline().strip().split()))
isa = lambda: stdin.readline().strip().split()
setrecursionlimit(100000)
mod = 1000000007

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

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

Solution (Python):
def solve():
  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):
      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+1:])
  return ans
print(solve())

Solution (Python):
import sys
input = sys.stdin.readline


N = int(input())


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




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

dp[0][0] = 1

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


res = 0.0
n = N // 2 + 1

for cnt in dp[-1][n:]:
    res += cnt

print(res)

Solution (Python):



N = int(input())


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




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

dp[0][0] = 1

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

res = 0.0
n = N // 2 + 1

for cnt in dp[-1][n:]:
    res += cnt

print(res)

Solution (Python):

"""
Created on Sun Jul 26 16:32:55 2020

@author: tinku
"""
n=int(input())
arr=list(map(float,input().split()))
dp=[[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):
    for j in range(n+1):
        if j==0:
            dp[i][j]=(1.0-arr[i-1])*dp[i-1][j]
        else:
            dp[i][j]=arr[i-1]*dp[i-1][j-1]+(1.0-arr[i-1])*dp[i-1][j]
print(sum(dp[n][n//2+1:]))

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

Solution (Python):
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):
        if j>0:
            dp[i][j]+=dp[i-1][j-1]*p[i-1]
        dp[i][j]+=dp[i-1][j]*(1-p[i-1])
print(sum(dp[n][n//2+1:]))

Solution (Python):
from sys import stdin
n = int(stdin.readline())
p = list(map(float,stdin.readline().split()))
dp = [[0]*(n+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(n+1):
    for j in range(n+1):
        if i>j:
            continue
        dp[i][j] += (0 if i==0 or j==0 else dp[i-1][j-1]*p[j-1])
        dp[i][j] += (0 if j==0 else dp[i][j-1]*(1-p[j-1]))
x = (n+1)//2
ans = 0
while x != n+1:
    ans += dp[x][-1]
    x += 1
print(ans)

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



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


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




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

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

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



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


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




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

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

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 j in range(i+2):
        if j ==0:
            dp[i][j]= dp[i-1][j]*(1-P[i])
        else:
            dp[i][j] = P[i]*dp[i-1][j-1] + (1-P[i])*dp[i-1][j]

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

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

Solution (Python):

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

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

Solution (Python):
import numpy as np
N = int(input())
dp = np.zeros(N+1, dtype=np.float64)
p_lst = list(map(float, input().split()))
dp[0] = 1
for p in p_lst:
  next_dp = dp * (1-p)
  next_dp[1:] += dp[:-1] * p
  dp = next_dp

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

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

Solution (Python):
import sys
input = sys.stdin.readline

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

D = [[0] * (n+1) for i in range(n+1)]
D[0][0] = 1
for i in range(1, n+1):
    for j in range(n+1):
        D[i][j] = D[i-1][j] * P[i-1]
        if j-1 >= 0:
            D[i][j] += D[i-1][j-1] * (1-P[i-1])

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

Solution (Python):
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(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)):
  ans += dp[N][i]
  
print(ans)

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

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

Solution (Python):
import numpy as np
n= int(input())
ppp = list(map(float,input().split()))
dp = np.array([0.0]*(n+1),dtype=np.float64)
dp[0]=1
for p in ppp:
  ndp = dp*(1-p)
  ndp[1:] += dp[:-1]*p
  dp = ndp
print(sum(dp[n//2+1:]))

Solution (Python):
import numpy as np
n= int(input())
ppp = list(map(float,input().split()))
dp = [0]*(n+1)
dp[0]=1
for p in ppp:
  ndp = [item*(1-p) for item in dp]
  ndp = [ndp[i] if i == 0 else ndp[i]+dp[i-1]*p for i in range(n+1)]
  dp = ndp
print(sum(dp[n//2+1:]))

Solution (Python):

def resolve():
    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.0 - P[i])

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


if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
readline = sys.stdin.readline





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)

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

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

Solution (Python):

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

Solution (Python):
n = int(input())
dp = [0] * (2 * n + 1)
dp[n] = 1
for p in map(float, input().split()):
    ndp = [0] * (2 * n + 1)
    for i in range(1, 2 * n):
        ndp[i-1] += dp[i] * (1 - p)
        ndp[i+1] += dp[i] * p
    dp = ndp
print(sum(dp[n+1:]))

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

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

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

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

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 9)





def input():
    return sys.stdin.readline().rstrip()


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

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

    n = (N+1)//2

    print(sum(dp[N][n:]))
    pass

if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import defaultdict as dd
from collections import deque
from fractions import Fraction as f
from copy import *
from bisect import *	
from heapq import *
from math import *
from itertools import permutations 
 
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
 

if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
def li():
	return [int(x) for x in input().split()]
def fli():
	return [float(x) for x in input().split()]	
def gi():	
	return [x for x in input().split()]
def fi():
	return int(input())
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())	
def gh():
	sys.stdout.flush()
def graph(n,m):
	for i in range(m):
		x,y=mi()
		a[x].append(y)
		a[y].append(x)
def bo(i):
	return ord(i)-ord('a')
		


tt=1



while tt>0:
	tt-=1
	n=fi()
	a=fli()
	dp=[[0 for i in range(n+1)] for j in range(n+1)]
	for i in range(n):
		if i==0:
			dp[i][0]=1-a[i]
			dp[i][1]=a[i]
		else:
			for j in range(0,n+1):
				dp[i][j]=dp[i-1][j]*(1-a[i])+(dp[i-1][j-1]*a[i] if j>0 else 0)
	ans=0			
	for i in range(n+1):
		if i>n-i:
			ans+=dp[n-1][i]
	print(ans)

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

Solution (Python):
import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  


N = ni()

p_array = list(map(float, stdin.readline().split()))

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

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


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

Solution (Python):
import sys
def main():
    N=int(sys.stdin.readline())
    p=[float(x) for x in sys.stdin.readline().split()]
    dp=[0 for _ in range(N+1)]
    dp[0]=1.0
    for i in range(1,N+1):
        for j in range(i,0,-1):dp[j]=dp[j-1]*p[i-1]+dp[j]*(1-p[i-1])
        dp[0]=dp[0]*(1-p[i-1])
    print(sum(dp[N//2+1:]))
if __name__=='__main__':main()

Solution (Python):
import sys
def main():
    N=int(sys.stdin.readline())
    p=[float(x) for x in sys.stdin.readline().split()]
    dp=[[0 for _ in range(N+1)] for _ in range(N+1)]
    dp[0][0]=1.0
    for i in range(1,N+1):
        dp[i][0]=dp[i-1][0]*(1-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])
    print(sum(dp[N][N//2+1:]))
if __name__=='__main__':main()

Solution (Python):
import sys
def main():
    N=int(sys.stdin.readline())
    p=[float(x) for x in sys.stdin.readline().split()]
    dp=[[0 for _ in range(N+1)] for _ in range(N+1)]
    dp[0][0]=1.0
    for i in range(1,N+1):
        dp[i][0]=dp[i-1][0]*(1-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//2+1:]))
if __name__=='__main__':main()

Solution (Python):
N = int(input())
p = list(map(float, input().split()))
dp = [[0.0 for i in range(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])
temp = (N+1)//2
print(sum(dp[-1][temp:]))

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

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