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: Runtime Error

Solution code:
import numpy as np

def Probability(p,n):
    dp = [[0 for i in range(n+1)] for j in range(n+1)]
   
    dp[0][0] = 1.0
    
    for i in range(1,n+1):
        for j in range(i+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]
    return ans 

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

 

print(Probability(a,n))

Submission status: Runtime Error

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-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]
    return ans 

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

 

print(Probability(a,n))

Submission status: Runtime Error

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
LI = lambda : [float(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N = NI()
p = LI()
dp = [0] * (N+1)
dp[0][0] = 1
for i in range(1,N+1):
    for j in range(0,i+1):
        if j > 0:
            dp[j] = dp[j-1] * p[i-1] + dp[j] * (1-p[i-1])
        else:
            dp[j] = dp[j] *  (1-p[i-1])

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

Submission status: Runtime Error

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
LI = lambda : [float(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N = NI()
p = LI()
dp = [0] * (N+1)
dp[0][0] = 1
for i in range(1,N+1):
    for j in range(0,i+1):
        if j > 0:
            dp[j] = dp[j-1] * p[i-1] + dp[j] * (1-p[i-1])
        else:
            dp[j] = dp[j] *  (1-p[i-1])

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

Submission status: Runtime Error

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]
a=0.0
for i in range((n+1)//2,n+1):
    a+=dp[n][i]
print(a)

Submission status: Runtime Error

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]
a=0.0
for i in range((n+1)//2,n+1):
  	a+=dp[n][i]
print(a)

Submission status: Runtime Error

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

dp = [1] + [0] * N
for p in enumerate(P):
    dp = [p * a + (1 - p) * b for a, b in zip([0] + dp, dp)]

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

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
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: Runtime Error

Solution code:
n=int(input())
p=list(map(float,input().split()))
x=1
for i in p:
    x*=(1-i)
l=[x]*n
s=x
ans=0
for i in range(1,n+1):
    l1=l.copy()
    x=0
    for j in range(n):
        l[j]=(((s-(i-1)*l1[j])/(1-p[j]))*p[j])/max(1,i-1)
        x+=l[j]
    s=x
    if i>=n//2+1:
        ans+=s/i
print(ans)

Submission status: Runtime Error

Solution code:

n = int(input())

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

B = [0] * (n + 1)

B[0] = 1

for x in A:
    for i in range(n, 0, -1):
        B[i] = (B[i - 1] * x + B[i] * (1 - x))
    B[0] *= (1 - x)

print(f"{sum(B[n // 2 + 1:]):.10f}")

Submission status: Runtime Error

Solution code:
def abc(l,n,a,b,c):
    if 2*(b+(n-c))<=n:
        return 0
    if c==n:
        return a
    return abc(l,n,a*l[c],b+1,c+1)+abc(l,n,a*(1-l[c]),b,c+1)
n=int(input())
l=list(map(float,input().split()))
d={}
ans=abc(l,n,1,0,0)
print(ans)

Submission status: Runtime Error

Solution code:
/******************************************
*    AUTHOR:         julianferres         *
******************************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define forr(i, a, b) for(int i = (a); i < (int) (b); i++)
#define forn(i, n) forr(i, 0, n)
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define DBG(x) cerr << #x << " = " << (x) << endl
#define esta(x,c) ((c).find(x) != (c).end())
#define RAYA cerr << "===============================" << endl


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

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

            


int main(){
    FIN;
    int n;
    cin >> n;
    vector<double> p(n, 0);
    forn(i, n) cin >> p[i];

    vector<vector<double>> dp(n, vector<double>(n + 1, 0));

    dp[0][1] = p[0];
    dp[0][0] = 1 - p[0];

    forr(i,1,n){
        dp[i][0] = dp[i - 1][0] * (1 - p[i]);
        forr(j, 1, n + 1) if (j <= i + 1)
            dp[i][j] = dp[i - 1][j - 1] * p[i] + dp[i - 1][j] * (1 - p[i]);
    }
    double sum = 0;
    forn(i, n + 1) if (i > n - i) sum += dp[n - 1][i];
    cout << fixed << setprecision(12) << sum << endl;

    return 0;
}

Submission status: Runtime Error

Solution code:
from decimal import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]

n = val()
l = li4()
mihe = n//2 + 1


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

for i in range(n-1,-1,-1):

    for j in range(i,n,1):
        sumarray[j] += ( l[i] / (1 - l[i]) ) * sumarray[j + 1]


curr = 1
for i in l:curr *= (1 - i)
ans = 0
for i in sumarray[:-mihe]:
    ans += i * curr
# if 'e' in str(ans):
temp = str(ans).index('e')
print((str(ans)[:temp + 1] + '0'*20)[:12])
# else:print(ans)

Submission status: Runtime Error

Solution code:
from decimal import Decimal as d,getcontext
getcontext().prec=5

a=int(input())
z=list(map(float,input().split()))
dp=[[0.0 for i in range(a+1)] for i in range(a)]
vi=[[0 for i in range(a+1)] for i in range(a)]
# i denotes the array i - n , j denotes the j heads


total=0.0
dp[a-1][0]=float(d(1)-d(z[-1]))
dp[a-1][1]=float(d(z[-1]))
vi[a-1][0]=1
vi[a-1][1]=1
total=0.0
def dps(i,j):
    
    if(a-i<j):
        return 0;
    if(i>=a or j>a):
        return 0;
    if(vi[i][j]):
        return dp[i][j];
    
    vi[i][j]=1
    dp[i][j]=z[i]*(dps(i+1,j-1))+(float(d(1)-d(z[i])))*dps(i+1,j)
    dp[i][j]=round(dp[i][j],8)
    return dp[i][j];
    
for i in range(a):
    for j in range(a+1):
        dp[i][j]=dps(i,j)
        
for i in range(a):
    if(i>=a//2):
        total=total+dp[0][i]

print(round(sum(dp[0][a//2+1:]),8))

Submission status: Runtime Error

Solution code:
sys.setrecursionlimit(10**5) 
N = int(input())
P = list(map(float, input().split()))
dp = [[-1 for p in range(N)] for n in range(N+1)]
# dp[0][0] = 1
def fn(reqd, pos):
	# print("HEY")
	if pos < 0 or reqd < 0:
		return 0	
	if reqd == 0:
		dp[reqd][pos] = 1
		return 1
	if reqd > pos+1:
		dp[reqd][pos] = 0
		return 0
	else:
		if pos != 0:
			dp[reqd][pos] = round((P[pos]*fn(reqd-1,pos-1)) + ((1-P[pos])*fn(reqd,pos-1)), 9)
			return dp[reqd][pos]
		else:
			if reqd == 1:
				dp[reqd][pos] = P[pos]
				return P[pos]
			else:
				dp[reqd][pos] = 0
				return 0
# for reqd in range(3, 1, -1):
# 	pos = N-1
	# print("HEY")
reqd = (N+1)//2
# print(reqd)
pos = N-1
print(fn(reqd, pos))
# print(dp)
	
# print(dp)

Submission status: Runtime Error

Solution code:
sys.setrecursionlimit(10**9) 
N = int(input())
P = list(map(float, input().split()))
dp = [[-1 for p in range(N)] for n in range(N+1)]
# dp[0][0] = 1
def fn(reqd, pos):
	# print("HEY")
	if pos < 0 or reqd < 0:
		return 0	
	if reqd == 0:
		dp[reqd][pos] = 1
		return 1
	if reqd > pos+1:
		dp[reqd][pos] = 0
		return 0
	else:
		if pos != 0:
			dp[reqd][pos] = round((P[pos]*fn(reqd-1,pos-1)) + ((1-P[pos])*fn(reqd,pos-1)), 9)
			return dp[reqd][pos]
		else:
			if reqd == 1:
				dp[reqd][pos] = P[pos]
				return P[pos]
			else:
				dp[reqd][pos] = 0
				return 0
# for reqd in range(3, 1, -1):
# 	pos = N-1
	# print("HEY")
reqd = (N+1)//2
# print(reqd)
pos = N-1
print(fn(reqd, pos))
# print(dp)
	
# print(dp)

Submission status: Runtime Error

Solution code:
N = int(input())
P = list(map(float, input().split()))
dp = [[-1 for p in range(N)] for n in range(N+1)]
# dp[0][0] = 1
def fn(reqd, pos):
	# print("HEY")
	if pos < 0 or reqd < 0:
		return 0	
	if reqd == 0:
		dp[reqd][pos] = 1
		return 1
	if reqd > pos+1:
		dp[reqd][pos] = 0
		return 0
	else:
		if pos != 0:
			dp[reqd][pos] = round(round(round(P[pos],9)*round(fn(reqd-1,pos-1), 9), 9) + round(round(1-P[pos], 9)*round(fn(reqd,pos-1), 9), 9), 9)
			return dp[reqd][pos]
		else:
			if reqd == 1:
				dp[reqd][pos] = P[pos]
				return round(P[pos], 9)
			else:
				dp[reqd][pos] = 0
				return 0
# for reqd in range(3, 1, -1):
# 	pos = N-1
	# print("HEY")
reqd = (N+1)//2
# print(reqd)
pos = N-1
print(fn(reqd, pos))
# print(dp)
	
# print(dp)

Submission status: Runtime Error

Solution code:
N = int(input())
P = list(map(float, input().split()))
dp = [[-1 for p in range(N)] for n in range(N+1)]
# dp[0][0] = 1
def fn(reqd, pos):
	# print("HEY")
	if pos < 0 or reqd < 0:
		return 0	
	if reqd == 0:
		dp[reqd][pos] = 1
		return 1
	if reqd > pos+1:
		dp[reqd][pos] = 0
		return 0
	else:
		if pos != 0:
			dp[reqd][pos] = round((P[pos]*fn(reqd-1,pos-1)) + ((1-P[pos])*fn(reqd,pos-1)), 9)
			return dp[reqd][pos]
		else:
			if reqd == 1:
				dp[reqd][pos] = P[pos]
				return P[pos]
			else:
				dp[reqd][pos] = 0
				return 0
# for reqd in range(3, 1, -1):
# 	pos = N-1
	# print("HEY")
reqd = (N+1)//2
# print(reqd)
pos = N-1
print(fn(reqd, pos))
# print(dp)
	
# print(dp)

Submission status: Runtime Error

Solution code:
N = int(input())
P = list(map(float, input().split()))
dp = [[-1 for p in range(N)] for n in range(N+1)]
# dp[0][0] = 1
def fn(reqd, pos):
	# print("HEY")
	if pos < 0 or reqd < 0:
		return 0	
	if reqd == 0:
		dp[reqd][pos] = 1
		return 1
	if reqd > pos+1:
		dp[reqd][pos] = 0
		return 0
	else:
		if pos != 0:
			dp[reqd][pos] = (P[pos]*fn(reqd-1,pos-1)) + ((1-P[pos])*fn(reqd,pos-1))
			return dp[reqd][pos]
		else:
			if reqd == 1:
				dp[reqd][pos] = P[pos]
				return P[pos]
			else:
				dp[reqd][pos] = 0
				return 0
# for reqd in range(3, 1, -1):
# 	pos = N-1
	# print("HEY")
reqd = (N+1)//2
# print(reqd)
pos = N-1
print(fn(reqd, pos))
# print(dp)
	
# print(dp)

Submission status: Runtime Error

Solution code:
N = int(input())
P = list(map(float, input().split()))
dp = [[-1 for p in range(N)] for n in range(N+1)]
dp[0][0] = 1
def fn(reqd, pos):
	# print("HEY")	
	if reqd == 0:
		dp[reqd][pos] = 1
		return 1
	if reqd > pos+1:
		dp[reqd][pos] = 0
		return 0
	else:
		if pos != 0:
			dp[reqd][pos] = (P[pos]*fn(reqd-1,pos-1)) + ((1-P[pos])*fn(reqd,pos-1))
			return dp[reqd][pos]
		else:
			if reqd == 1:
				dp[reqd][pos] = P[pos]
				return P[pos]
			else:
				dp[reqd][pos] = 0
				return 0
# for reqd in range(3, 1, -1):
# 	pos = N-1
	# print("HEY")
reqd = (N+1)//2
# print(reqd)
pos = N-1
print(fn(reqd, pos))
# print(dp)
	
# print(dp)

Submission status: Runtime Error

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

def dfs(cur, n, p, cnt, res, memo):
  if cur == n:
    if cnt > 0:
      return res
    return 0
  if (cur, cnt, res) in memo:
    return memo[(cur, cnt, res)]
  r = dfs(cur+1, n, p, cnt+1, res*p[cur], memo) + dfs(cur+1, n, p, cnt-1, res*(1-p[cur]), memo)
  memo[(cur, cnt, res)] = r
  return memo[(cur, cnt, res)]

print(dfs(0, n, p, 0, 1, {}))

Submission status: Runtime Error

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

def prob(n,k):
  if prob_memo[n][k]==-1:
    prob_memo[n][k] = prob(n-1,k-1)*P[n-1] + prob(n-1,k)*(1-P[n-1])
  return prob_memo[n][k]

def prob_ret():
  ret = 0
  for k in range(N//2+1,N+1):
    ret += prob(N,k)
  return ret

print(prob_ret())

Submission status: Runtime Error

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

dp = [[None] * 1501 for i in range(3000)]
def dfs(i=0, at=(n + 1) // 2):
    if i == n:
        return int(at <= 0)
    if dp[i][at] is not None:
        return dp[i][at]

    r = dfs(i + 1, at - 1) * a[i] + dfs(i + 1, at) * (1 - a[i])
    dp[i][at] = r
    return r

print(dfs())

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(float,input().split()))
K = N//2 + 1


def dfs(i,K):
    if (i,K) in cache: return cache[(i,K)]
    if K < 0: 
        cache[(i,K)] = 1
        return 1
    if i>=N: 
        cache[(i,K)] = 1
        return 1
    if len(A[i:]) < K: 
        res = (1-A[i])*dfs(i+1,K)
    elif len(A[i:]) == K: 
        res = A[i]*dfs(i + 1,K-1)
    else:
        res = A[i]*dfs(i+1,K-1) + (1-A[i])*dfs(i+1,K)
    cache[(i,K)] = res
    return res
cache={}
print(dfs(0,K))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(float,input().split()))
K = N//2 + 1


def dfs(i,K):
    if (i,K) in cache: return cache[(i,K)]
    if i>=N: 
        cache[(i,K)] = 1
        return 1
    if len(A[i:]) < K: 
        res = (1-A[i])*dfs(i+1,K)
    elif len(A[i:]) == K: 
        res = A[i]*dfs(i + 1,K-1)
    else:
        res = A[i]*dfs(i+1,K-1) + (1-A[i])*dfs(i+1,K)
    cache[(i,K)] = res
    return res
cache={}
print(dfs(0,K))

Submission status: Runtime Error

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

dp_list = [[0]*(n+1) for i in range(n)]

def dp(i, j):
  if dp_list[i][j] == 0:
    if i == 0:
      if j == 0:
        dp_list[i][j] = 1-p[i]
      if j == 1:
        dp_list[i][j] = p[i]
    elif j-i == 1:
      dp_list[i][j] = dp(i-1, j-1)*p[i]
    elif j == 0:
       dp_list[i][j] = dp(i-1, j)*(1-p[i])
    else:
      dp_list[i][j] = dp(i-1, j)*(1-p[i]) + dp(i-1, j-1)*p[i]
  return dp_list[i][j]

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

Submission status: Runtime Error

Solution code:
from functools import lru_cache
def head_prob(N,p):
    @lru_cache(None)
    def f(i,k):
        if i <0 or k <0: return 0
        if i == 0 and k == 1:
            return p[0]
        if i == 0 and k == 0:
            return 1 - p[0]
        return p[i]*f(i-1,k-1) + (1-p[i])*f(i-1,k)

    probs = [(f(N-1,k),k) for k in range(1,N+1)]
    return sum(prob[0] for prob in probs if prob[1] > N/2)



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

Submission status: Runtime Error

Solution code:
N = int(input())
p_f = [0]
p_b = [0]
for p in list(map(float,input().split())):
    p_f.append(p)
    p_b.append(1.0-p)

p_majority = 0.0
n_majority = N // 2 + 1

def cointoss(n_toss,n_front,n_back,p):
    global p_majority
    n_toss += 1
    #print(n_toss,n_front,n_back,p,p_majority,n_majority)
    if n_front+1 == n_majority:
        p_majority = p_majority + p * p_f[n_toss]
    else:
        cointoss(n_toss, n_front+1, n_back, p*p_f[n_toss])
    if n_back+1 == n_majority:
        return
    cointoss(n_toss, n_front, n_back+1, p*p_b[n_toss])

cointoss(0,0,0,1.0)
print(p_majority)

Submission status: Runtime Error

Solution code:
#include<iostream>
#include <vector>
#include <iomanip>
using namespace std;

int main()
{    
    int N;
    cin >> N;

    double dp[N+1][N+1]={};
    double p[N];

    for (int i = 0; i < N; ++i) { 
        cin >> p[i];
    }
    
    dp[1][0]=1-p[0];
    dp[1][1]=p[0];
    
    for (int i = 2; i < N+1; ++i) { 
        dp[i][0]=dp[i-1][0]*(1-p[i-1]);
        for (int j = 1; j < N+1; ++j) {
             dp[i][j]=dp[i-1][j]*(1-p[i-1])+dp[i-1][j-1]*p[i-1];
        }
    }

    double ans=0;
    for (int i = (N+1)/2; i < N+1; ++i) { 
        ans+=dp[N][i];
    }
    cout << fixed << setprecision(10) << ans << endl;
    return 0;

}

Submission status: Runtime Error

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

# probs[i][k] : コインiまでを投げて表がk枚出る確率
probs = [[None for _ in range(N+1)] for _ in range(N)]

probs[0][1] = Ps[0]
probs[0][0] = 1 - Ps[0]
for i in range(2, N+1):
  probs[0][i] = 0

sum_all = 0
sum_ok  = 0
start = int(N/2) + 1

for i in range(1, N):
  for k in range(0, N+1):
    if k == 0:
      probs[i][k] = probs[i-1][k]*(1-Ps[i])
    else:
      probs[i][k] = probs[i-1][k-1]*Ps[i] + probs[i-1][k]*(1-Ps[i])
    if i == N - 1:
      sum_all += probs[i][k]
      if k >= start:
        sum_ok += probs[i][k]


# print(probs)

# sum_all = sum(probs[N-1])
# sum_ok = 0

# start = int(N/2) + 1
# for i in range(start, N+1):
#   sum_ok += probs[N-1][i]

print(sum_ok / sum_all)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define pu push
#define pp pop_back
#define in insert
#define MOD 1000000007
#define endl "\n"
#define sz(a) (int)((a).size())
#define all(x) (x).begin(), (x).end()
#define trace(x) cerr << #x << ": " << x << " " << endl;
#define prv(a) for(auto x : a) cout << x << ' ';cout << '\n';
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define OTP(s) cout<<s<<endl;
#define FOR(i,j,k,l) for(int i=j;i<k;i+=l)
#define REP(i,j) FOR(i,0,j,1)
inline ll add(ll a, ll b){a += b; if(a >= MOD)a -= MOD; return a;}
inline ll sub(ll a, ll b){a -= b; if(a < 0)a += MOD; return a;}
inline ll mul(ll a, ll b){return (ll)((ll) a * b %MOD);}
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;

ll min(ll a,ll b)
{
    return a>b?b:a;
}
ll max(ll a,ll b)
{
    return a>b?a:b;
}

ll n;
double q[3000][3000];
double p[10000];
int main()
{
    IOS
    cin>>n;
    REP(i,n)
    {
        cin>>p[i+1];
    }
    double prod=1;

    q[0][0]=1;
    FOR(i,1,n+1,1)
    {
        prod*=0;
        q[0][i]=prod;
    }
    prod=1;
    REP(i,n)
    {
        prod*=p[i+1];
        q[i+1][0] = prod;
    }
    FOR(i,1,n+1,1)
    {
        FOR(j,1,i+1,1)
        {
            q[i][j] = p[i]*q[i-1][j] + (1-p[i])*q[i-1][j-1];
        }
    }
    // REP(i,n+1)
    // {
    //     REP(j,n+1)
    //     {
    //         cout<<q[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    double ans = 0;
    REP(i,(n-1)/2+1)
    {
        ans+=q[n][i];
    }
    cout<<fixed<<setprecision(12)<<ans<<endl;
}

Submission status: Runtime Error

Solution code:
import numpy as np


n = int(input())
p = [float(x) for x in input().split()]
dp = np.zeros((n+1,n+1))
dp[0][1] =  p[0]
dp[0][0] = 1-p[0]
for i  in range(n):
    if i<=0:
        continue
    dp[i][0] = dp[i-1][0]*(1-p[i])
    for j in range(i+1):
        dp[i][j+1] = dp[i-1][j]*p[i]
        dp[i][j+1] += dp[i-1][j+1]*(1-p[i])

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

Submission status: Runtime Error

Solution code:

def total(p,cp,seq):
    global prob
    if cp==len(p):
        # print(seq)
        h = 0
        for i in range(cp):
            if seq[i]=="Head":
                h+=1
        if h>cp//2:
            curProb = 1
            for i in range(cp):
                if seq[i]=="Head":
                    curProb = curProb*p[i]
                else:
                    curProb = curProb*(1-p[i])
            prob += curProb

        return
    seq[cp] = "Head"
    total(p,cp+1,seq)

    seq[cp] = "Tail"
    total(p,cp+1,seq)

prob = 0
n = int(input())
p = list( map(float,input().split()))
seq = [ "" for i in range(n)]
total(p,0,seq)
print(prob)

Submission status: Runtime Error

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(100000000)
N = int(input())
def main():
    a = list(map(int, input().split()))
    d = {0:0, 1:0, 2:0, 3:0}
    for i in a:
        d[i] += 1
    print(dfs(d[1],d[2],d[3]))
@lru_cache(maxsize=None)
def dfs(a, b, c):
    if a + b + c == 0:
        return 0
    t1 = t2 = t3 = 0
    total = a + b + c
    if a > 0:
        t1 = (a/total) * dfs(a-1, b, c)
    if b > 0:
        t2 = (b/total) * dfs(a+1, b-1, c)
    if c > 0:
        t3 = (c/total) * dfs(a, b+1, c-1)
    return N/total + t1 + t2 + t3
main()

Submission status: Runtime Error

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

def solve(coin, flip_res, total_tails):
    #print("solve(" + str(coin) + ", " + str(flip_res) + ", " + str(total_tails) + ")")
    if total_tails > N/2:
            #print("Total_tails > N/2")
            return 0
    if coin == N-1:
        if flip_res:
            #print("value(coin==N-1 and tails): " + str(1 - p_ar[coin]))
            return 1 - p_ar[coin]
        else:
            #print("value(coin==N-1 and heads): " + str(p_ar[coin]))
            return p_ar[coin]
    else:
        if flip_res:
            a = (1 - p_ar[coin]) * (solve(coin + 1, 0, total_tails) + solve(coin + 1, 1, total_tails + 1)) 
            #print("value(coin1=N-1 and tails): " + str(a))
            return a
        else:
            a = p_ar[coin] * (solve(coin + 1, 0, total_tails) + solve(coin + 1, 1, total_tails + 1)) 
            #print("value(coin1=N-1 and heads): " + str(a))
            return a

print(solve(0, 0, 0) + solve(0, 1, 1))

Submission status: Runtime Error

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] =0
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: Runtime Error

Solution code:
n = int(input())
p = [float(x) for x in input().strip().split()]
dp = {}
def solve(i,k):
    if i in dp and k in dp[i]:
        return dp[i][k]
    if k<=0:
        if i not in dp:
            dp[i] ={}
        dp[i][k] = 1
    elif k>n-i:
        if i not in dp:
            dp[i] ={}
        dp[i][k] = 0
    elif i>n-1:
        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: Runtime Error

Solution code:
#include <bits/stdc++.h>
#include <vector>
#include <cmath>
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP2(i, m, n) for (int i = (m); i < (int)(n); ++i)
#define REPR(i, n) for (int i = (n)-1; i >= 0; --i)
#define REPR2(i, m, n) for (int i = (n)-1; i >= (m); --i)
#define REPx(x, a) for(auto x : a)
#define ALL(a) a.begin(), a.end()
#define SORT(a) sort(ALL(a))
#define SORTR(a) sort(ALL(a), greater<int>())
#define REVERSE(a) reverse(ALL(a))
#define bit_search(bit, n) REP(bit, 1<<(n))
#define bit_check(bit, i) (bit>>(i)) & 1
#define setpre(n) fixed << setprecision((n))
#define UNIQUE(a) do {SORT(a); (a).erase(unique(ALL(a)), (a).end());} while(0)
#define MAX(a) *max_element(ALL(a))
#define MIN(a) *min_element(ALL(a))
#define bisect_left(a, x) lower_bound(ALL(a), (x)) - a.begin()
#define bisect_right(a, x) upper_bound(ALL(a), (x)) - a.begin()
#define INPUT(a) REP(i, a.size()) cin >> a[i];
#define INPUTP(a) REP(i, a.size()) cin >> a[i].first >> a[i].second;
#define ENDL cout << endl;
using namespace std;
using LL = long long;
using ld = long double;
using PII = pair<int, int>;
using VPII = vector<PII>;
using PLL = pair<LL, LL>;
using VPLL = vector<PLL>;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VC = vector<char>;
using VS = vector<string>;
using VB = vector<bool>;
const int INF = 1e9;
const LL MOD = 1e9 + 7;

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<double> p(N);
  INPUT(p);
  vector<vector<double>> dp(N+1, vector<double>(N+1, 0));
  dp[0][0] = 1;
  REP2(i, 1, N+1) REP(j, N+1)
  {
    if (j > i) continue;
    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];
  }
  double ans = 0;
  REP2(i, N/2+1, N+1) ans += dp[N][i];
  cout << setpre(10) << ans << endl;

  return 0;
}

Submission status: Runtime Error

Solution code:
# At DP I
def solve(P):
    dp = {}

    def solveX(P, index, head):
        n = len(P)
        if index >= n:
            tail = n - head
            if head > tail:
                return 1
            return 0
        if (index, head) in dp:
            return dp[(index, head)]
        sum_ = P[index] * solveX(P, index + 1, head + 1)
        sum_ += (1 - P[index]) * solveX(P, index + 1, head)
        dp[(index, head)] = sum_
        return sum_
    return solveX(P, 0, 0)

assert solve([0.30, 0.60, 0.80]) == 0.612
assert solve([0.42, 0.01, 0.42, 0.99, 0.42]) == 0.38218158719999995


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

Submission status: Runtime Error

Solution code:
# At DP I
def solve(P):
    dp = {}

    def solveX(P, index, head):
        n = len(P)
        if index >= n:
            tail = n - head
            if head > tail:
                return 1
            return 0
        if (index, head) in dp:
            return dp[(index, head)]
        sum_ = P[index] * solveX(P, index + 1, head + 1)
        sum_ += (1 - P[index]) * solveX(P, index + 1, head)
        dp[(index, head)] = sum_
        return sum_
    return solveX(P, 0, 0)

assert solve([0.30, 0.60, 0.80]) == 0.612
assert solve([0.42, 0.01, 0.42, 0.99, 0.42]) == 0.38218158719999995


n = int(input())
P = map(float, input().split())
ans = solve(P)
print(ans)

Submission status: Runtime Error

Solution code:
# At DP I
def solve(P):
    dp = {}

    def solveX(P, index, head):
        n = len(P)
        if index >= n:
            tail = n - head
            if head > tail:
                return 1
            return 0
        if (index, head) in dp:
            return dp[(index, head)]
        sum_ = P[index] * solveX(P, index + 1, head + 1)
        sum_ += (1 - P[index]) * solveX(P, index + 1, head)
        dp[(index, head)] = sum_
        return sum_
    return solveX(P, 0, 0)

assert solve([0.30, 0.60, 0.80]) == 0.612
assert solve([0.42, 0.01, 0.42, 0.99, 0.42]) == 0.38218158719999995


n = int(input())
P = map(float, input().split())
ans = prob(P, 0, len(P))
print(ans)

Submission status: Runtime Error

Solution code:
# At DP I
def solve(P):
    dp = {}

    def solveX(P, index, head):
        n = len(P)
        if index >= n:
            tail = n - head
            if head > tail:
                return 1
            return 0
        if (index, head) in dp:
            print("hit")
            return dp[(index, head)]
        sum_ = P[index] * solveX(P, index + 1, head + 1)
        sum_ += (1 - P[index]) * solveX(P, index + 1, head)
        dp[(index, head)] = sum_
        return sum_
    return solveX(P, 0, 0)

assert solve([0.30, 0.60, 0.80]) == 0.612
print(solve([0.42, 0.01, 0.42, 0.99, 0.42]))
assert solve([0.42, 0.01, 0.42, 0.99, 0.42]) == 0.38218158719999995


n = int(input())
P = map(float, input().split())
ans = prob(P, 0, len(P))
print(ans)

Submission status: Runtime Error

Solution code:
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]))
		#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 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.coinToss()