Problem:


Score : 100 points

Problem Statement

Let N be a positive odd number.

There are N coins, numbered 1, 2, \ldots, N.
For each i (1 \leq i \leq N), when Coin i is tossed, it comes up heads with probability p_i and tails with probability 1 - p_i.

Taro has tossed all the N coins.
Find the probability of having more heads than tails.

Constraints

N is an odd number.

1 \leq N \leq 2999

p_i is a real number and has two decimal places.

0 < p_i < 1

Input

Input is given from Standard Input in the following format:

N
p_1 p_2 \ldots p_N

Output

Print the probability of having more heads than tails.
The output is considered correct when the absolute error is not greater than 10^{-9}.

Sample Input 1

3
0.30 0.60 0.80

Sample Output 1

0.612

The probability of each case where we have more heads than tails is as follows:

The probability of having (Coin 1, Coin 2, Coin 3) = (Head, Head, Head) is 0.3 × 0.6 × 0.8 = 0.144;

The probability of having (Coin 1, Coin 2, Coin 3) = (Tail, Head, Head) is 0.7 × 0.6 × 0.8 = 0.336;

The probability of having (Coin 1, Coin 2, Coin 3) = (Head, Tail, Head) is 0.3 × 0.4 × 0.8 = 0.096;

The probability of having (Coin 1, Coin 2, Coin 3) = (Head, Head, Tail) is 0.3 × 0.6 × 0.2 = 0.036.

Thus, the probability of having more heads than tails is 0.144 + 0.336 + 0.096 + 0.036 = 0.612.

Sample Input 2

1
0.50

Sample Output 2

0.5

Outputs such as 0.500, 0.500000001 and 0.499999999 are also considered correct.

Sample Input 3

5
0.42 0.01 0.42 0.99 0.42

Sample Output 3

0.3821815872



Sample input:
3
0.30 0.60 0.80


Sample output:
0.612

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    P = [float(v) for v in 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:]))

main()

Submission status: Accepted

Solution code:
import sys

def solve(N: int, p: "List[float]"):
    #dp[i][j]: i枚投げて、j枚表の確率
    dp=[[0]*(N+1) for _ in range(N+1)]

    dp[0][0]=1

    # dp[1][0]=dp[0][0]*p[1]
    # dp[1][1]=dp[0][0]*(1-p[1])

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

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

    print(ans)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    p = [float(next(tokens)) for _ in range(N)]  # type: "List[float]"
    solve(N, p)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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


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

Submission status: Accepted

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

# dp[i][j] = i回目にコインを投げたとき、面がj個になっている確率
dp = [[0] * (N + 1) for i in range(N + 1)]

dp[0][0] = 1
for i in range(1, N + 1):
  for j in range(N + 1):
    if j - 1 < 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]) # 裏が出てj+1個になる確率と表が出てj+1個になる確率

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
P = list(map(float,input().split()))
dp = [[0] * (n+1) for i in range(n+1)]
dp[0][0] = 1

for i in range(n):
  pi = P[i]
  for j in range(n):
    dp[i+1][j+1] += dp[i][j] * pi
    dp[i+1][j] += dp[i][j] * (1 - pi)
print(sum(dp[n][n//2+1:]))
# print(dp)

Submission status: Accepted

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

Submission status: Accepted

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

dp = [[.0 for _ 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])

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

#print(dp)
print(ans)

Submission status: Accepted

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

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

print(sum(dp[-1][n2+1:]))

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res
 
def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)
 
 
 
        
def main(): #startline--------------------------------------------
    n = int(input())
    p = list(map(float,input().split()))
    dp = [[0]*(n+1) for i in range(n+1)]
    #dp[i][j]...i枚のコインを投げたときに表がj枚でる確率
    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])
 
    ans = 0
    for i in range((n+1)//2,n+1):
        ans += dp[n][i]
    print(ans)
 
if __name__ == "__main__":
    main() #endline==============================================

Submission status: Accepted

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    p0_list = np.array([float(item) for item in input().split()])
    p1_list = 1 - p0_list

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

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

N = int(input())
p0_list = np.array([float(item) for item in input().split()])
p1_list = 1 - p0_list

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

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

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

Submission status: Accepted

Solution code:
N = int(input()) # number of coins
tmp = [float(i) for i in input().split()]
dp = [0 for i in range(N+1)] # 0 - N heads
dp[0] = 1
# initialize
for i in range(N):
  k = tmp[i]
  # when the very first coin comes we need to verify update format
  # 1 head or 1 tails
  # j is the number of heads which goes from 0 - N
  for j in range(i+1, -1, -1):
    dp[j] = dp[j-1] * k + dp[j] * (1-k)
ans = 0
for i in range(N+1):
  tails = N-i
  if tails < i:
    ans += dp[i]
print("%s" % ans)

Submission status: Accepted

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

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

dp[0][0] = 1

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

ans = 0
for i in range(N+1)[::-1]:
    if i > (N - i):        
        ans += dp[N][i]

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
  import numpy as np
  n=int(input())
  p=np.array([float(i) for i in input().split()])
  
  dp=np.zeros([n+1,n+1],dtype=np.float64)
  dp[0][0]=1
  for i in range(n):
    tmp=np.roll(dp[i],1)
    tmp[0]=0
    dp[i+1]+=dp[i]*(1-p[i])+tmp*p[i]
    

  print(sum(dp[n][(n+1)//2:]))
      
if __name__=='__main__':
  main()

Submission status: Accepted

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

Submission status: Accepted

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

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

for i in range(n-1):
  for j in range(i+2):
    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: Accepted

Solution code:
def main():
    import sys
    readline = sys.stdin.readline

    n = int(readline())
    *p, = (float(pi) for pi in readline().rstrip().split())

    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    # dp[投げた枚数][表の枚数] = 確率

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

    ret = sum(dp[n][j] for j in reversed(range(n + 1)) if j * 2 > n)
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
P = list(map(float, input().split()))
dp = np.zeros((n+1, n+1))
dp[0, 0] = 1
for i in range(n):
  dp[i+1, 0] = dp[i, 0] * (1-P[i])
  dp[i+1, 1:] = dp[i, :-1]*P[i] + dp[i, 1:]*(1-P[i])
print(dp[n, 1+n//2:].sum())

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    p=list(map(float,input().split()))
    dp=[[float(0)]*(N+1) for _ in range(N+1)]
    dp[0][0]=float(1)
    for i in range(N):
        for omote in range(i+2):
            dp[i+1][omote]+=dp[i][omote]*(1-p[i])
            if omote>=1:
                dp[i+1][omote]+=dp[i][omote-1]*p[i]
    ans=0
    for i in range(-(-(N+1)//2)):
        ans+=dp[N][-(1+i)]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from copy import copy
N = int(input())
P = list(map(float,input().split()))
dp = [0. for i in range(N+1)]
for i in range(N):
    if i == 0:
        dp[0] = 1. - P[i]
        dp[1] = P[i]
    else:
        new_dp = copy(dp)
        for j in range(N+1):
            if j == 0:
                new_dp[j] = dp[j]*(1-P[i])
            else:
                new_dp[j] = dp[j]*(1-P[i]) + dp[j-1]*(P[i])
        dp = copy(new_dp)
print(sum(dp[N//2+1:]))

Submission status: Accepted

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

Submission status: Accepted

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

#dp[i][h] = i+1番目までで表h枚の確率
dp = [[0]*(N+1) for i in range(N)]
dp[0][0] = 1-p[0]
dp[0][1] = p[0]

for i in range(1, N):
  for h in range(N+1):
    dp[i][h] = dp[i-1][h]*(1-p[i]) + (0 if h==0 else dp[i-1][h-1]*p[i])
    
print(sum(dp[N-1][int((N+1)/2):]))

Submission status: Accepted

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

# dp[i][j] i回目でj回表がでる確率
dp = [[0 for j in range(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][j+1] += pl[i] * dp[i][j]
        dp[i+1][j] += (1-pl[i]) * dp[i][j]

def ceil(a, b):
   return a // b + (a % b > 0)
print(sum(dp[-1][ceil(n,2):]))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n=int(input())
P=[0]+list(map(float,input().split()))
#dp[i][j]i枚目まででj枚表が出る。
dp=[[0]*(n+1) for i in range(n+1)]
dp[1][0]=1-P[1]
dp[1][1]=P[1]
if n==1:
    print(P[1])
else:
    for i in range(2,n+1):
        for j in range(i+1):
            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]
    ans=0
    for i in range((n+1)//2):
        ans+=dp[n][i]
    print(1-ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()
arr=list(map(float,sys.stdin.readline().rstrip().split()))

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

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

Submission status: Accepted

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

# コインをn回投げて、表がj枚の確率
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(n):
        dp[i+1][j+1] = dp[i][j] * p[i] + dp[i][j+1] * (1-p[i])
print(sum(dp[n][(n+1)//2:]))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
P = tuple(map(float, input().split()))

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

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

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

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
P = np.array(input().split(), dtype=float)

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

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

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

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
P = np.array(input().split(), dtype=float)

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

for i in range(N - 1):
    newDP = dp * (1 - P[i + 1])
    newDP[1:] += dp[:-1] * P[i + 1]
    dp = newDP.copy()

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

Submission status: Accepted

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

#i枚投げて，j枚が表である確率
dp=[[0]*(N+1) for _ in range(N+1)]

dp[0][0]=1

for i in range(N):
    for j in range(N):
        dp[i+1][j]+=dp[i][j]*(1-p[i])
        dp[i+1][j+1]+=dp[i][j]*p[i]
        if j==i:
            break
            
print(1.0-sum(dp[-1][:N//2+1]))

Submission status: Accepted

Solution code:
n = int(input())
p = list(map(float, input().split()))
#dp[i][j] := i枚目のコインを投げ、表がj枚の確率 
#遷移式は、今回のコインが表が出るか、裏が出るかのみ考えればよい
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):
    k = p[i-1]
    for j in range(i+1):
        #さっきj枚達成してたら、裏じゃなきゃいけない
        #さっきはj-1しか達成できてないなら、今回は表
        if j > 0:
            dp[i][j] += (dp[i-1][j-1] * k) + (dp[i-1][j] * (1 - k))
        else:
            dp[i][j] += dp[i-1][j] * (1 - k)
ans = 0
for i in range(n+1):
    if (n - i) < i:
        ans += dp[-1][i]
print(ans)

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

N = iin()
p = fln()

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

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def add_mod(a,b): return (a+b) % MOD

N = iin()
p = fln()

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

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
MOD = 10**9+7

N = iin()
p = fln()

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

Submission status: Accepted

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

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

  # sum all probabilies where heads > tails
  ans = sum(dp[N // 2 + 1:])
  print(ans)


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


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

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
MOD = 10**9+7

N = iin()
p = fln()

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

Submission status: Accepted

Solution code:
def solve():
    N, *p = map(float, open(0).read().split())
    N = int(N)

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

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


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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


dp[0][N-1] = 1 - prob_table[0]
dp[0][N+1] =   prob_table[0]

for i in range(1,N):
	for j in range(N-i-1,N+i+2):
		if(j > 0 and j < 2*N+1):
			dp[i][j] = dp[i-1][j-1]*prob_table[i] + dp[i-1][j+1]*(1-prob_table[i])
		elif(j <= 0):
			dp[i][j] = dp[i-1][j+1]*(1-prob_table[i])
		else : 
			dp[i][j] = dp[i-1][j-1]*prob_table[i]
print(sum(dp[N-1][N+1:]))

Submission status: Accepted

Solution code:
#Educational DP Contest
#I-Coins

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

#dp table
dp = [[0.0]*(n+1) for _ in range(n+1)] #確率を0で初期化(2次元)
dp[0][0] = 1.0 #0番目は存在しないので1で初期化(単位元のような感じ。乗算だから単位元は1)


#process1
#dp[i][j]は、i回までのコインを投げて、j枚が表の確率。
#つまり、ループの内側がn回表の確率、外側がコインの枚数となる
#但し、i回までのコインでi枚以上の表は出ないので、jのループはi迄とする。
"""
図にするとこんなかんじ
    0回表,1回表,2回表...
0枚目[[1.0, 0.0, 0.0, 0.0],
1枚目[0.7, 0.3, 0.0, 0.0], #0.7で1枚中0枚が表,0.3で1枚中1枚が表
2枚目[0.28, 0.54, 0.18, 0.0],
3枚目[0.056, 0.33, 0.468, 0.144]] #0.056+0.33で半分未満が表、0.468+0.144で半分以上が表
"""
for i in range(1,n+1):
    for j in range(i+1): #jはピラミッド状に増えていく
        dp[i][j] = dp[i-1][j]*(1-lst1[i-1]) #裏になる確率
        if j > 0: #j-1を参照できるなら
            dp[i][j] += dp[i-1][j-1]*lst1[i-1] #表になる確率

#output process
#問題はdp[i][j] >= 0.5となる確率なので、j>= 0.5 = 表の枚数/全体の枚数
#となるj以上の確率の合計が答え(ちなみに、任意のdp[i]の合計sum(dp[i]) == 1となる)
ans = 0.0
for i in range((n+1)//2,n+1): #j(表が出る枚数)が半分以上のところから全部のところまでの確率の合計
    ans += dp[-1][i]
print(ans)

Submission status: Accepted

Solution code:
#Educational DP Contest
#I-Coins

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

#dp table
dp = [[0.0]*(n+1) for _ in range(n+1)] #確率を0で初期化(2次元)
dp[0][0] = 1.0 #0番目は存在しないので1で初期化(単位元のような感じ。乗算だから単位元は1)


#process1
#dp[i][j]は、i回までのコインを投げて、j枚が表の確率。
#つまり、ループの内側が表の確率、外側がコインの枚数となる
#但し、i回までのコインでi枚以上の表は出ないので、jのループはi迄とする。
"""
図にするとこんなかんじ(1列目は実際に起きる数字ではない)
[[1.0, 0.0, 0.0, 0.0],
[0.7, 0.3, 0.0, 0.0], #0.7で裏,0.3で表
[0.28, 0.54, 0.18, 0.0],
[0.056, 0.33, 0.468, 0.144]] #0.056+0.33で裏、0.468+0.144で表
"""
for i in range(1,n+1):
    for j in range(i+1):
        dp[i][j] = dp[i-1][j]*(1-lst1[i-1])
        if j > 0:
            dp[i][j] += dp[i-1][j-1]*lst1[i-1]

#output process
#問題はdp[i][j] >= 0.5となる確率なので、j>= 0.5 = 表の枚数/全体の枚数
#となるj以上の確率の合計が答え(ちなみに、任意のdp[i]の合計sum(dp[i]) == 1となる)
ans = 0.0
for i in range((n+1)//2,n+1): #j(表が出る枚数)が半分以上のところから全部のところまでの確率の合計
    ans += dp[-1][i]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(float,input().split()))
dp = [[0 for i in range(n)] for i in range(n//2+1)]
for i in range((n//2)+1):
    l,j=1,i
    while j<n:
        if i==0:
            l=l*a[j]
            dp[i][j]=l
            j=j+1
        else:
            for k in range(i):
                l=l*(1-a[k])
                dp[i][k]=l
            while j<n:
                dp[i][j]=(dp[i-1][j-1]*(1-a[j]))+(dp[i][j-1]*a[j])
                j=j+1
l=0
for i in range(n//2+1):
    l+=dp[i][n-1]
print(l)

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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[(N+1)//2])

Submission status: Accepted

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

dp = [[0.0 for _ in range(3002)] for _ in range(3002)]
dp[0][0] = 1

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

answer = 0
for  j in range(N // 2 + 1, 3002):
  answer += dp[N][j]

print(answer)

Submission status: Accepted

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

dp = np.zeros(len(p)+1)
dp[0] = 1 - p[0]
dp[1] = p[0]

for i in range(1, len(p)):
    ura = dp * (1 - p[i])
    omote = np.append(np.zeros(1), dp[:-1] * p[i])
    dp = ura + omote

print(np.sum(dp[len(p)//2+1:]))

Submission status: Accepted

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

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

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


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