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: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
p = [0] + list(input().split())

for i in range(1, N+1):
    item = p[i].replace('0.', '')
    p[i] = int(item)

#print(p)

dp = [[0 for a in range(3100)] for b in range(3100)]
#dp[i][j] = i枚目までのコインを投げて，表の個数がj枚である確率 * (10**(2*i))

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

for i in range(2, N + 1):
    for j in range(1, i+1):
        dp[i][j] = (dp[i-1][j-1] * p[i] + dp[i-1][j] * (100-p[i])) // 10 ** max(0, i-10)
        #dp[i][j] = i-1枚目までで表がj-1かつi回目で表　＋　i-1回目までで表がj枚かつi回目で裏（MECE）
        #print(i, j, dp[i][j])
        #プログラムの仕組み上，iが一つ進むと，100 * 100 = 10**4　ずつスケールが大きくなっていく。10**20で打ち切る。


ans = 0

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

dig = min(2*N, 10)

print(ans/10**dig)

Submission status: Wrong Answer

Solution code:
N = int(input())
p = [0] + list(input().split())

for i in range(1, N+1):
    item = p[i].replace('0.', '')
    p[i] = int(item)

print(p)

dp = [[0 for a in range(3100)] for b in range(3100)]
#dp[i][j] = i枚目までのコインを投げて，表の個数がj枚である確率 * (10**(2*i))

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

for i in range(2, N + 1):
    for j in range(i+1):
        dp[i][j] = (dp[i-1][j-1] * p[i] + dp[i-1][j] * (100-p[i])) // (10**max(0, i - 20))
        #dp[i][j] = i-1枚目までで表がj-1かつi回目で表　＋　i-1回目までで表がj枚かつi回目で裏（MECE）
        #print(i, j, dp[i][j])
        #プログラムの仕組み上，iが一つ進むと，100 * 100 = 10**4　ずつスケールが大きくなっていく。10**20で打ち切る。


ans = 0

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

dig = min(2*N, 20)

print(ans/10**dig)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def coins(n,prob):
    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]*prob[i-1]
            else:
                dp[i][j] = dp[i-1][j]*(1-prob[i-1])+dp[i-1][j-1]*prob[i-1]
    total = 0
    for i in range(n,n//2,-1):
        total+= dp[n][i]
    return total

n = int(input())
prob = list(map(float,input().split()))
print(coins(n,prob))

Submission status: Wrong Answer

Solution code:
prob = []
lim = 0

import sys
sys.setrecursionlimit(100000)

def main():
    global prob, lim
    n = int(input())
    lim = n//2 + 1
    
    prob = [float(x) for x in input().split()]
    dp = [[-1]*(n + 1) for _ in range(n + 1)]
    
    print(coins(n, 1, 0, dp))
    
def coins(n, p, k, dp):
    global prob, lim
    
    if k == lim:
        if dp[n][k] != -1:
            dp[n][k] += p
        else:
            dp[n][k] = p
        return dp[n][k]
    
    if n == 0 or k + n < lim:
        dp[n][k] = 0
        return dp[n][k]

    
    dp[n][k] = coins(n - 1, p*(1 - prob[n-1]), k, dp) + coins(n - 1, p*prob[n-1], k + 1, dp)
    return dp[n][k]


        
main()

Submission status: Wrong Answer

Solution code:
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]))
        dp[i][j] = round(dp[i][j],10)
x = (n+1)//2
ans = 0
while x != n+1:
    ans += dp[x][-1]
    x += 1
print(ans)

Submission status: Wrong Answer

Solution code:
a = 0.732489355323423

ans = 0
for i in range(1000):
  ans += a
  
print(ans)

ans = 0
for i in range(1000):
  ans += round(a, 10)
  
print(ans)

Submission status: Wrong Answer

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_i
import math
N = int(input())
P_List = list(map(float,input().split()))
dp = [[] * N for i in range(N+1)]
std = math.ceil(N/2)
for i in range(N+1):
    if i == 0:
        dp[0].append(1)
    else:
        Current_P = P_List[i - 1]
        for j in range(i + 1):
            if (N - i + j) < std:
                dp[i].append(0)
            elif j == 0:
                dp[i].append(round(dp[i - 1][j]*(1 - Current_P),10))
            elif j != i:
                dp[i].append(round((dp[i - 1][j]*(1 - Current_P)) + (dp[i - 1][j - 1]*Current_P),10))
            else:
                dp[i].append(round(dp[i - 1][j - 1]*Current_P,10))
    
print(sum(dp[N]))

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
P_List = list(map(float,input().split()))
dp = [[] * N for i in range(N+1)]

for i in range(N+1):
    if i == 0:
        dp[0].append(1)
    else:
        Current_P = P_List[i - 1]
        for j in range(i + 1):
            if j == 0:
                dp[i].append(round(dp[i - 1][j]*(1 - Current_P),10))
            elif j != i:
                dp[i].append(round((dp[i - 1][j]*(1 - Current_P)) + (dp[i - 1][j - 1]*Current_P),10))
            else:
                dp[i].append(round(dp[i - 1][j - 1]*Current_P,10))
    
print(sum(dp[N][math.ceil(N/2):]))

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
P_List = list(map(float,input().split()))
dp = []
for i in range(N):
    Current_Fault_P,Current_Correct_P = 1-P_List[i],P_List[i]
    if i == 0:
        dp.append([Current_Fault_P,Current_Correct_P])
    else:
        dp.append([])
        for j in dp[i-1]:
            dp[i].append(round(j*Current_Fault_P,9))
            dp[i].append(round(j*Current_Correct_P,9))

Standard = math.ceil(N/2)
Ans = 0
for k in range(len(dp[-1])):
    if bin(k).count("1") >= Standard:
       Ans += dp[-1][k]

print(round(Ans,10))

Submission status: Wrong Answer

Solution code:
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):
        dp[0]=dp[0]*(1-p[i-1])
        for j in range(1,i+1):dp[j]=dp[j-1]*p[i-1]+dp[j]*(1-p[i-1])
    print(sum(dp[N//2+1:]))
if __name__=='__main__':main()

Submission status: Wrong Answer

Solution code:
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):
        dp[0]=dp[0]*(1-p[i-1])
        for j in range(1,N+1):dp[j]=dp[j-1]*p[i-1]+dp[j]*(1-p[i-1])
    print(sum(dp[N//2+1:]))
if __name__=='__main__':main()

Submission status: Wrong Answer

Solution code:
n = int(input())
p = list(map(float, input().split()))
dp =  [[0 for j in range(n+1)] for i in range(n+1)]

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.00-p[i])
ans = 1.00
for i in range(int((n+1)/2)):
    ans -= dp[n][i]
print("{:.6f}".format(ans))

Submission status: Wrong Answer

Solution code:
from decimal import Decimal

N = int(input())
p = [i for i in map(Decimal, input().split(" "))]

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

for i in dp:
    print(i)

res = Decimal(0.0)
for i in range(N//2+1, N+1):
    res += dp[N][i]
print("{:.10f}".format(res))

Submission status: Wrong Answer

Solution code:
N = int(input())
p = [i for i in 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])

for i in dp:
    print(i)

res = 0.0
for i in range(N//2+1, N+1):
    res += dp[N][i]
print("{:.10f}".format(res))

Submission status: Wrong Answer

Solution code:
n=int(input())
import math
p=list(map(float,input().split()))
dp=[[0]*(n) for i in range(n+1)]
dp[0][0]=(1-p[0])
for i in range(1,n):
    dp[0][i]=round(dp[0][i-1]*(1-p[i]),10)
# print(dp[0][1],1-p[2],dp[0][1]*(1-p[2]))
for i in range(1,n+1):
    for j in range(i-1,n):
        if j==0:
            temp1=1 
            temp2=0 
        else:
            temp1=dp[i-1][j-1]
            temp2=dp[i][j-1]
        dp[i][j]=temp1*p[j]+temp2*(1-p[j])
        dp[i][j]=round(dp[i][j],10)
ans=0
# print(dp)
for i in range(n//2+1,n+1):
    ans+=dp[i][n-1]
print(ans)

Submission status: Wrong Answer

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


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


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


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

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

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

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

    print(cur)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
h=list(map(float,input().split()))
t=[]
for i in range(n+1):
    temp=[1]*(n+1)
    t.append(temp)
for i in range(1,n+1):
    for j in range(i+1):
        if j==0:
            t[i][j]=t[i-1][j-1]*(1-h[i-1])
        elif i==j:
            t[i][j]=t[i-1][j-1]*(h[i-1])
        else:
            t[i][j]=t[i-1][j-1]*(h[i-1])+t[i-1][j]*(1-h[i-1])
a=0
for i in range(n//2+1,n+1):
    a+=t[n][i]
print(a)

Submission status: Wrong Answer

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] = 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: Wrong Answer

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

# dp[i][j]: 最初のi枚を投げたときに表がj枚となる確率
dp = [[0] * (n + 1) for _ 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 - p[i]) # 裏

res = 0
print(dp)
for j in range(n + 1):
	if n < 2 * j: # 表の枚数 > 裏の枚数
		res += dp[n][j]

print(res)

Submission status: Wrong Answer

Solution code:
# Python3 implementation of the above approach 
import numpy as np 

# Function to return the probability when 
# number of heads is greater than 
# the number of tails 
def Probability(p, n) : 

	# Declaring the DP table 
	dp = np.zeros((n + 1, n + 1)); 
	for i in range(n + 1) : 
		for j in range(n + 1) : 
			dp[i][j] = 0.0

	# Base case 
	dp[0][0] = 1.0; 

	# Iterating for every coin 
	for i in range(1, n + 1) : 

		# j represents the numbers of heads 
		for j in range(i + 1) : 

			# If number of heads is equal to zero 
			# there there is only one possiblity 
			if (j == 0) : 
				dp[i][j] = dp[i - 1][j] * (1.0 - p[i]); 
			else : 
				dp[i][j] = (dp[i - 1][j] * (1.0 - p[i]) +
							dp[i - 1][j - 1] * p[i]); 
	
	ans = 0.0; 

	# When the number of heads is greater than (n+1)/2 
	# it means that heads are greater than tails as 
	# no of tails + no of heads is equal to n for 
	# any permuation of heads and tails 
	for i in range((n + 1)// 2, n + 1) : 
		ans += dp[n][i]; 

	return ans; 

# Driver Code 
if __name__ == "__main__" : 
	
	# 1 based indexing 
	p = [ 0.0, 0.3, 0.4, 0.7 ]; 

	# Number of coins 
	n = len(p) - 1; 

	# Function call 
	print(Probability(p, n)); 

# This code is contributed by AnkitRai01

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
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: Wrong Answer

Solution code:
n=int(input())
from fractions import Fraction
from copy import copy
p=list(map(float,input().split()))
x=1
for i in p:
    i=Fraction(i)
    x*=(1-i)
l=[x]*n
s=x
ans=0
for i in range(1,n+1):
    l1=copy(l)
    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(float(ans))

Submission status: Wrong Answer

Solution code:
n=int(input())
p=list(map(float,input().split()))
from copy import copy
x=1
for i in p:
    x*=(1-i)
l=[x]*n
s=x
ans=0
for i in range(1,n+1):
    l1=copy(l)
    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: Wrong Answer

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]

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

dp = np.zeros(N+1, dtype=float)
dp[0] = 1

for c in P:
#    prev = dp.copy()
    dp = np.append(dp[:-1] * (1-c), 0) + np.append(0, dp[:-1] * c)
    print(dp)

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

Submission status: Wrong Answer

Solution code:
N = int(input())
P = [float(v) for v in input().split()]
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]

for i,p in enumerate(P,1): dp[i][0] = (1-p)
dp[0][0] = 1

threshold = N // 2


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

ans = 0


for i,v in enumerate(dp[N]):
    if i > threshold:
        ans += v
print(ans)

Submission status: Wrong Answer

Solution code:
n = 1
p = [0.5]

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

Submission status: Wrong Answer

Solution code:
N = int(input())
P = [float(v) for v in input().split()]
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]

for i,p in enumerate(P,1): dp[i][0] = (1-p)
dp[0][0] = 1

threshold = N // 2


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

ans = 0

#  for r in dp:
    #  print(r)

for i,v in enumerate(dp[N]):
    if i > threshold:
        ans += v
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# I-Coin

'''
5
0.42 0.01 0.42 0.99 0.42
'''


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

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

# i=0: 0枚中j(>0)枚が表の確率 = 0
dp[0][0] = 1

# j=0: i(>0)枚中0枚が表の確率 = 全て裏の確率
for i in range(1, N + 1):
    dp[i][0] = dp[i - 1][0] * (1 - p[i - 1])

# 漸化式で更新
for i in range(1, N + 1):
    for j in range(1, N + 1):
        dp[i][j] = dp[i-1][j-1] * p[i - 1] + dp[i-1][j] * (1 - p[i - 1])

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

Submission status: Wrong Answer

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

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

# for i, p in enumerate(P):
#     p2 = 1 - p
#     for j in range(i + 1, -1, -1):
#         if j >= 0:
#             dp[j] = dp[j] * p2 + dp[j - 1] * p
#         else:
#             dp[j] = dp[j] * p2

# ldp = len(dp)
# s = ldp - len(dp) // 2

# print(sum(dp[s:]))

Submission status: Wrong Answer

Solution code:
import numpy as np

n = int(input())

dp = np.zeros(n)
dp[0] = 1.

for p in map(float, input().split()):
  tmp = (1. - p) * dp
  tmp[1:] += p * dp[:-1]
  dp = tmp

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

Submission status: Wrong Answer

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(float,input().split()))

n = ii()
p =li()

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

Submission status: Wrong Answer

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


curr = 1
for i in l:curr *= (1 - i)
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]


ans = 0
for i in sumarray[:-mihe]:
    ans += i *curr

print(round(ans,10))

Submission status: Wrong Answer

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: Wrong Answer

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):print((str(ans) + '0'*20)[:12])
else:print(ans)

Submission status: Wrong Answer

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
print((str(ans) + '0'*20)[:12])

Submission status: Wrong Answer

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]

dp = [0]*(n + 1)

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

    
    for j in range(n):sumarray[j] += dp[j]
    print(dp)


# for i in dp:print(*i)
# print(*sumarray)

curr = 1
for i in l:curr *= (1 - i)
ans = 0
for i in sumarray[:-mihe]:
    ans += i * curr
print(ans)

Submission status: Wrong Answer

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


dp = [[0.0000000000000 for i in range(n)] for j in range(n + 1)]
sumarray = [1.00000000000 for i in range(n + 1)]



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

    for j in range(n):
        if sumarray[j] != 1:
            sumarray[j] += dp[i][j]
        else:
            sumarray[j] = dp[i][j]



# for i in dp:print(*i)
# print(*sumarray)

curr = 1
for i in l:curr *= (1 - i)

print(sum(j * curr for j in sumarray[:- mihe]))

Submission status: Wrong Answer

Solution code:
from math import ceil

n = int(input())
parr = 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(0,n+1):
        if j == 0:
            dp[i][j] = dp[i-1][j] * (1-parr[i-1])
        else:
            dp[i][j] = dp[i-1][j-1] * parr[i-1] + dp[i-1][j] * (1-parr[i-1])
print(ceil(n/2))
print(sum(dp[-1][ceil(n/2):]))

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque
import copy

N = int(input())
p = list(map(float, input().split()))
if N == 1:
    print(p[0])
    sys.exit()
dp = [[0 for _ in range(N + 10)] for _ in range(N + 10)]
dp[2][0] = (1.0 - p[0]) * (1.0 - p[1])
dp[2][2] = p[0] * p[1]
dp[2][1] = 1.0 - dp[2][0] - dp[2][2]
for i in range(3, N + 1):
    for l in range(1, N + 1):
        dp[i][l] = dp[i - 1][l] * (1.0 - p[i - 1]) + dp[i - 1][l - 1] * p[i - 1]
ans = 0.0
for i in range(N // 2 + 1, N + 1):
    ans += dp[N][i]
print(math.ceil(ans*10**10)/10**10)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque
import copy

N = int(input())
p = list(map(float, input().split()))
if N == 1:
    print(p[0])
    sys.exit()
dp = [[0 for _ in range(N + 10)] for _ in range(N + 10)]
dp[2][0] = (1.0 - p[0]) * (1.0 - p[1])
dp[2][2] = p[0] * p[1]
dp[2][1] = 1.0 - dp[2][0] - dp[2][2]
for i in range(3, N + 1):
    for l in range(1, N + 1):
        dp[i][l] = dp[i - 1][l] * (1.0 - p[i - 1]) + dp[i - 1][l - 1] * p[i - 1]
ans = 0.0
for i in range(N // 2 + 1, N + 1):
    ans += dp[N][i]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque
import copy

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

if N == 1:
    print(p[0])
    sys.exit()
dp = [[0 for _ in range(N + 10)] for _ in range(N + 10)]
dp[2][0] = (1 - p[0]) * (1 - p[1])
dp[2][2] = p[0] * p[1]
dp[2][1] = 1 - dp[2][0] - dp[2][2]
for i in range(3, N + 1):
    dp[i][0] = dp[i - 1][0] * p[i - 1]
for i in range(3, N + 1):
    for l in range(1, N + 1):
        dp[i][l] = dp[i - 1][l] * (1 - p[i - 1]) + dp[i - 1][l - 1] * p[i - 1]
ans = 0
for i in range(N//2+1, N+1):
    ans += dp[N][i]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4000)

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

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

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

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

Submission status: Wrong Answer

Solution code:
def solve(N, probs):
  # dp[i][j]: probability of having j heads in i coin tosses
  dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
  dp[0][0] = 1

  for toss_id in range(1, N + 1):
    head_prob = probs[toss_id - 1]
    tail_prob = 1 - probs[toss_id - 1]
    # only until i needed
    for j in range(toss_id + 1):
      # zero heads
      if j == 0:
        dp[toss_id][j] += dp[toss_id - 1][j] * tail_prob
      else:
        dp[toss_id][j] += (dp[toss_id - 1][j] * tail_prob) + \
          (dp[toss_id - 1][j - 1] * head_prob)

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


def iin(): return int(input())
def fln(): return list(map(float, input().split()))


N = iin()
probs = fln()
solve(N, probs)

Submission status: Wrong Answer

Solution code:
def task(probs):
    n = len(probs)
    dp = [0] * (n + 1)
    dp[0] = 1

    for i, p in enumerate(probs, start=1):
        prev = 0
        for j in range(i + 1):
            dp[j] = dp[j] * (1 - p) + prev
            prev = dp[j] * p

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


n = input()  # n
probs = [float(x) for x in input().split()]
print(task(probs))

Submission status: Wrong Answer

Solution code:
def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista

def wczytaj_rzeczywiste():
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(float(element))
    return ostateczna_lista

def rzuc_grosza_wiedzminowi_migusiem():
    N = wczytaj_liste()[0]
    prawdopodopienstwa = wczytaj_rzeczywiste()
    przed_rzutem = [1.0]
    for moneta in prawdopodopienstwa: 
        po_rzucie = []
        for i in range(len(przed_rzutem)):
            if i > 0: 
                print(i, przed_rzutem)
                po_rzucie.append(przed_rzutem[i]*(1-moneta)+przed_rzutem[i-1]*(moneta))
            else:
                po_rzucie.append(przed_rzutem[0]*(1-moneta))
        po_rzucie.append(przed_rzutem[-1]*moneta)
        przed_rzutem = po_rzucie
    odp = sum(przed_rzutem[N//2+1:])
    print(odp)
    
rzuc_grosza_wiedzminowi_migusiem()