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:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    """
    N個の足場があります。足場には1,2,…,Nと番号が振られています。 
    各i (1≤i≤N) について、足場 i の高さは hi です。
    最初、足場 1 にカエルがいます。 カエルは次の行動を何回か繰り返し、足場 N まで辿り着こうとしています。
    足場 i にいるとき、足場 i+1 または i+2 へジャンプする。
    このとき、ジャンプ先の足場を j とすると、コスト |hi−hj| を支払う。
    カエルが足場 N に辿り着くまでに支払うコストの総和の最小値を求めてください。

    制約
        入力はすべて整数である。
    2≤N≤10**5
    1≤hi≤10**4
    """
    n = II()
    h = LI()
    dp = [0 for i in range(n)]
    dp[1] = abs(h[0] - h[1])
    for i in range(2,n):
        dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]))
    print(dp[n-1])
    return

#B
def B():
    n, K = LI()
    h = LI()
    dp = [float("INF") for i in range(n + K + 1)]
    dp[0] = 0
    for i in range(n):
        for k in range(1, K + 1):
            if i + k >= n:
                break
            dp[i + k] = min(dp[i + k], dp[i] + abs(h[i] - h[i + k]))
    print(dp[n-1])
    return

#C
def C():
    n = II()
    abc = LIR(n)
    dp = [0 for i in range(3 * n + 1)]
    dp[0] = abc[0][0]
    dp[1] = abc[0][1]
    dp[2] = abc[0][2]
    for i in range(1,n):
        dp[3 * i] = max(dp[3 * i], dp[3 * (i - 1) + 1] + abc[i][0], dp[3 * (i - 1) + 2] + abc[i][0])
        dp[3 * i + 1] = max(dp[3 * i + 1], dp[3 * (i - 1) + 2] + abc[i][1], dp[3 * (i - 1)] + abc[i][1])
        dp[3 * i + 2] = max(dp[3 * i + 2], dp[3 * (i - 1) + 1] + abc[i][2], dp[3 * (i - 1)] + abc[i][2])
    dp[3 * n] = max(dp)
    print(dp[3*n])

    return

#D
def D():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**5
    1≤wi≤W
    1≤vi≤10**9"""
    n, w = LI()
    wv = LIR(n)
    dp = [[0 for k in range(w + 1)] for i in range(n + 2)]
    for i in range(1,n + 1):
        for j in range(w + 1):
            if j < wv[i-1][0]:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - wv[i - 1][0]] + wv[i - 1][1])
    print(dp[n+1][w])

    
    return

#E
def E():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**9
    1≤wi≤W
    1≤vi≤10**3"""
    n, w = LI()
    wv = LIR(n)
    dp = [[float("INF") for i in range(10 ** 5 + 1)] for k in range(n + 1)]
    dp[0][0] = 0
    for i in range(n):
        for k in range(10 ** 5 + 1):
            if k < wv[i][1]:
                dp[i + 1][k] = dp[i][k]
            else:
                dp[i + 1][k] = min(dp[i][k], dp[i][k - wv[i][1]] + wv[i][0])
    ans = 0
    for i in range(10 ** 5 + 1):
        if dp[n][i] <= w:
            ans = i
    print(ans)

    return

#F
def F():
    s = "abc"*1000
    t = "abc"*1000
    dp = [[0 for i in range(len(t)+1)] for k in range(len(s)+1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                if dp[i][j + 1] < dp[i + 1][j]:
                    dp[i + 1][j + 1] = dp[i + 1][j]
                else:
                    dp[i + 1][j + 1] = dp[i][j + 1]
        
    print(dp[len(s)][len(t)])
    return

#G
def G():
    n, m = LI()
    xy = LIR_(m)
    edge = [[] for i in range(n)]
    for x,y in xy:
        edge[x].append(y)
    dp = [0 for i in range(n)]
    def ans(dp, i):
        #print(dp, i)
        if dp[i] != 0:
            return dp[i]
        else:
            if len(edge[i]) == 0:
                return 0
            ansb = 0
            for k in edge[i]:
                #print(dp, k , i)
                ansb = max(ansb, ans(dp, k) + 1)
                dp[i] = max(ansb, dp[i])
                #print(dp)
            return ansb
            
    for i in range(n):
        dp[i] = ans(dp, i)
    print(max(dp))
    return

#H
def H():
    h, w = LI()
    a = SR(h)
    dp = [[0 for i in range(w)] for k in range(h)]
    for i in range(w):
        if a[0][i] == "#":
            break
        dp[0][i] = 1
    for i in range(h):
        if a[i][0] == "#":
            break
        dp[i][0] = 1
    for i in range(1,w):
        for k in range(1, h):
            #print(i,k, dp)
            if a[k - 1][i] == ".":
                if a[k][i - 1] == ".":
                    dp[k][i] = dp[k - 1][i] + dp[k][i - 1] % mod
                else:
                    dp[k][i] = dp[k - 1][i]
            else:
                if a[k][i - 1] == ".":
                    dp[k][i] = dp[k][i - 1]
    print(dp[h-1][w-1] % mod)

    return

#I
def I():
    n = II()
    p = LF()
    dp = [[0 for k in range(n+1)] for i in range(n+1)]
    dp[1][1] = p[0]
    dp[1][0] = 1-p[0]
    for i in range(2,n+1):
        for k in range(i + 1):
            if k == 0:
                
                dp[i][k] = dp[i-1][k] * (1 - p[i-1])
            else:
                dp[i][k] = dp[i - 1][k - 1] * p[i - 1] + dp[i - 1][k] * (1 - p[i - 1])
    #print(dp)
    print(sum(dp[n][n//2+1:]))
    return 
#J

#K


#L

#M
#N
# O
# P
# Q
# R
# S
# T
# U
# V
# W
# X
# Y
# Z


#Solve
if __name__ == '__main__':
    I()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    n = I()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n-2):
        dp[i+1] = min(dp[i+1],dp[i]+abs(h[i+1]-h[i]))
        dp[i+2] = min(dp[i+2],dp[i]+abs(h[i+2]-h[i]))
    dp[n-1] = min(dp[n-1],dp[n-2]+abs(h[n-1]-h[n-2]))
    print(dp[n-1])
#B
def B():
    n,k = LI()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n):
        for j in range(1,min(n-i,k+1)):
            dp[i+j] = min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
    print(dp[n-1])

#C
def C():
    n = I()
    v = LIR(n)
    dp = [[0,0,0] for i in range(n+1)]
    for i in range(n):
        dp[i+1][0] = max(dp[i+1][0],dp[i][1]+v[i][0],dp[i][2]+v[i][0])
        dp[i+1][1] = max(dp[i+1][1],dp[i][2]+v[i][1],dp[i][0]+v[i][1])
        dp[i+1][2] = max(dp[i+1][2],dp[i][0]+v[i][2],dp[i][1]+v[i][2])
    print(max(dp[n]))

#D
def D():
    n,W = LI()
    g = LIR(n)
    dp = [[0 for i in range(W+1)] for j in range(n+1)]
    for i in range(n):
        for j in range(W+1)[::-1]:
            w,v = g[i]
            if j >= w:
                dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
            else:
                dp[i+1][j] = max(dp[i+1][j],dp[i][j])
    print(max(dp[n]))
#E
def E():
    n,W = LI()
    g = LIR(n)
    V = 100000
    dp = [[float("inf") for i in range(V+1)] for j in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(V+1)[::-1]:
            w,v = g[i]
            if j >= v:
                dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)
            else:
                dp[i+1][j] = min(dp[i+1][j],dp[i][j])

    for i in range(V+1)[::-1]:
        if dp[n][i] <= W:
            print(i)
            quit()

#F
def F():
    s = S()
    t = S()
    dp = [[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i+1][j+1] = max(dp[i][j]+1,dp[i+1][j],dp[i][j+1])
            else:
                dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])

    i = len(s)
    j = len(t)
    ans = ""
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:i -= 1
        elif dp[i][j] == dp[i][j-1]:j -= 1
        else:
            i -= 1
            j -= 1
            ans = s[i]+ans
    print(ans)
#G
def G():
    n,m = LI()
    e = LIR(m)
    dp = [0 for j in range(m+1)]
    for i in range(m):
        x,y = e[i]
        dp[i+1][y] = max(dp[i][y],dp[i][x]+1)
    ans = 0
    for i in range(m+1):
        ans = max(dp[i])
    print(ans)
#H
def H():
    h,w = LI()
    s = SR(h)
    dp = [[0 for i in range(w)] for j in range(h)]
    dp[0][0] = 1
    for i in range(h-1):
        for j in range(w-1):
            if s[i+1][j] == ".":
                dp[i+1][j] += dp[i][j]
                dp[i+1][j] %= mod
            if s[i][j+1] == ".":
                dp[i][j+1] += dp[i][j]
                dp[i][j+1] %= mod
    for j in range(w-1):
        if s[h-1][j+1] == ".":
            dp[h-1][j+1] += dp[h-1][j]
            dp[h-1][j+1] %= mod
    for i in range(h-1):
        if s[i+1][w-1] == ".":
            dp[i+1][w-1] += dp[i][w-1]
            dp[i+1][w-1] %= mod
    print(dp[h-1][w-1])

#I
def J():
    n = I()
    p = list(map(float, input().split()))
    dp = [[0 for i in range(n+1)] for j in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        for j in range(n+1):
            dp[i+1][j] = p[i]*dp[i][j-1]+(1-p[i])*dp[i][j]

    ans = 0
    m = math.floor(n/2)
    for i in range(m+1,n+1):
        ans += dp[n][i]
    print(ans)
#Solve
if __name__ == "__main__":
    J()

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys


n = int(input())
p = list(map(float, sys.stdin.readline().rstrip().split()))

dp = [0.0] * (n+1)
dp[0] = 1

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

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
g = np.array(list(map(float,input().split())))
dp = np.zeros(n+1)
dp[0] = 1.0

for i in range(n):
  dp = np.roll(dp*g[i],1) + dp*(1-g[i])
print(sum(dp[n//2+1:]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

def f3(n, p):
    dp = [ 0.0 ] * (n + 1)
    dp[0] = 1.0
    for i in range(n):
        pi_ = 1 - p[i]
        dp = [dp[j - 1] * p[i] + dp[j] * pi_ \
            for j in range(n + 1)]
    return(sum(dp[n // 2 + 1:]))

n = int(input()) # n: odd, 1 <= n <= 2999
p = list(map(float, input().split())) # 0 < pi[i] < 1
print(f3(n, p))

Submission status: Accepted

Solution code:
"""
I - Coins

考え方:
    N 枚のコインを投げた時, n 枚表になる確率を求める.
    以下の二つの和で求められる(①).
        N - 1 枚投げた時に n - 1 枚表になり, さらに次に投げた時に表になる確率
        N - 1 枚投げた時に n 枚表になり, さらに次に投げた時に裏になる確率
    N を0から始めるとDPで求められる.
    0 <= n <= N / 2 となるすべての n の確立の和が表が半分以下となる確率 X.
    表が半分以上となる(裏より多くなる)確率は 1 - X.
    計算量は O(n^2) <- あってる？？
"""


def solve():
    N = int(input())
    P = [float(i) for i in input().split()]
    dp = [1 for i in range(int((N + 1) / 2))]  # i 枚表になる確率
    for i, p in enumerate(P, 1):
        for j in reversed(range(len(dp))):
            if i <= j:
                # コインの合計枚数が i 枚以下の場合は表にする.
                dp[j] *= p
            elif j == 0:
                # 表のコインの枚数が 0 枚の場合は普通に裏になる.
                dp[j] *= (1 - p)
            else:
                # N 枚のコインを投げて n 枚表になる(①の計算)
                dp[j] = dp[j] * (1 - p) + dp[j - 1] * p
    print(1 - sum(dp))


if __name__ == '__main__':
    solve()

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(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, i+1):
        dp[i][j] = dp[i-1][j-1]*p[i-1] + dp[i-1][j]*(1-p[i-1])
        #print(dp, sep='\n')        
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[投げたコイン枚数][表のコイン枚数] 
dp = [[0]*(n+1) for i in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
  dp[i][0] = dp[i-1][0]*(1-p[i-1])
  dp[i][i] = dp[i-1][i-1]*p[i-1]
  for j in range(1,i):
    dp[i][j] = dp[i-1][j]*(1-p[i-1])+dp[i-1][j-1]*p[i-1]
print(sum(dp[n][(n+1)//2:]))

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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


# dp[i][j] : i枚目までで表がj枚の確率

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

for i in range(N + 1):
    dp[0][i] = 0.0
dp[0][0] = 1.0

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

res = 0
for i in range(N + 1):
    if i > N // 2:
        res += dp[N][i]

print(res)

Submission status: Accepted

Solution code:
n = int(input())
p = list(map(float, input().split()))
dp = [[0.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+1):
        if j == 0:
            dp[i+1][0] = dp[i][0] * (1 - p[i])
        else:
            dp[i+1][j] = dp[i][j-1] * p[i] + dp[i][j] * (1-p[i])
print(1 - sum(dp[n][:(n+1)//2]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python2
from __future__ import division, print_function

import os
import sys
from atexit import register
from io import BytesIO

range = xrange

sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

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

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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python2
"""
This file is part of https://github.com/cheran-senthil/PyRival
Copyright 2019 Cheran Senthilkumar <hello@cheran.io>

"""
from __future__ import division, print_function

import itertools
import math
import os
import sys
from atexit import register
from io import BytesIO


class dict(dict):
    """dict() -> new empty dictionary"""

    def items(self):
        """D.items() -> a set-like object providing a view on D's items"""
        return dict.iteritems(self)

    def keys(self):
        """D.keys() -> a set-like object providing a view on D's keys"""
        return dict.iterkeys(self)

    def values(self):
        """D.values() -> an object providing a view on D's values"""
        return dict.itervalues(self)


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


range = xrange

filter = itertools.ifilter
map = itertools.imap
zip = itertools.izip

sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

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

dp = [[0.0] * (n + 1) for _ in range(n)]
dp[0][0], dp[0][1] = 1 - p[0], p[0]

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

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

Submission status: Accepted

Solution code:
import numpy as np

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

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

for i in P:
    tmp = dp * (1-i)
    #スライスさせて掛算
    tmp[1:] += dp[:-1] * i
    dp = tmp

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

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
import numpy as np

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    P = LF()

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

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

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


print(main())

Submission status: Accepted

Solution code:
# coding:utf-8

import sys

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    P = LF()

    # dp[i]: i枚のコインが表になる確率
    dp = [1]

    # 調和級数
    # O(NlogN)
    for i in range(n):
        tmp = [0] * (i + 2)
        p = P[i]
        q = 1 - P[i]
        for j in range(i + 1):
            tmp[j] += dp[j] * q
            tmp[j + 1] += dp[j] * p
        dp = tmp

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


print(main())

Submission status: Accepted

Solution code:
def main(): 
  N = int(input())
  p = list(map(float, input().split()))
  
  if N == 1:
    print(p[0])
    return 
  Ans = N // 2 + 1
  
  DP = [[0 for i in range(N + 1)] for j in range(N)]
  DP[0][0] = 1 - p[0]
  DP[0][1] = p[0]
  
  for i in range(1, N):
    DP[i][0] = DP[i - 1][0] * (1 - p[i])
    for j in range(1, N // 2 + 1):
      DP[i][j] = (DP[i - 1][j - 1] * p[i] + DP[i - 1][j] * (1 - p[i]))
    DP[i][Ans] = DP[i - 1][Ans - 1] * p[i] + DP[i - 1][Ans]
  print(DP[i][Ans])
  
main()

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
p = list(lf())
dp = [[0]*(n+1) for _ in range(n+1)]

dp[0][0] = 1
for o in range(n):
    for u in range(n):
        if o+u >= n:
            continue
        
        dp[o][u+1] += (1-p[o+u]) * dp[o][u]
        dp[o+1][u] += p[o+u] * dp[o][u]
        
ans = 0
for o in range(n+1):
    u = n-o
    if o > u:
        ans += dp[o][u]
        
print(ans)

Submission status: Accepted

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

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

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

m = (len(dp[-1])+1) // 2
print(sum(dp[-1][m:]))

Submission status: Accepted

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = input()
p = map(float, raw_input().strip().split())

dp = [[0 for i in xrange(n + 1)] for j in xrange(n + 1)]
dp[0][0] = 1

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

ans = 0
for k in xrange(n + 1):
    if 2 * k > n: ans += dp[i][k]

print "{0:.10f}".format(ans)

Submission status: Accepted

Solution code:
n=int(input())
ans=[None]*(n+1)
for i in range(n+1):
  ans[i]=[0]*(n+1)
l=list(map(float,input().split()))
for i in range(n+1):
  ans[0][i]=0
for i in range(1,n+1):
  for j in range(0,n+1):
    if(i==1):
      if(j==0):
        ans[i][j]=1-l[0]
        continue
      elif(j==1):
        ans[i][j]=l[0]
        continue
      else:
        break
    if(j==0):
      ans[i][0]=ans[i-1][0]*(1-l[i-1])
      continue
    ans[i][j]=ans[i-1][j-1]*l[i-1] + ans[i-1][j]*(1-l[i-1])
a=0
import math
for i in range(math.ceil(n/2),n+1):
  a+=ans[n][i]
print(a)

Submission status: Accepted

Solution code:

n = input()
p = map(float, raw_input().split())

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

Submission status: Accepted

Solution code:
n=int(input())
p=list( float(s) for s in input().split() )
res=[1-p[0], p[0]]+[0]*(n//2 - 1)
for i in range(1,n):
    p1=p[i]
    p0=1-p[i]
    res[len(res)-1]=p0*res[len(res)-1]
    for j in range(len(res)-2, -1, -1):
        res[j+1]+=(res[j]*p1)
        res[j]=(res[j]*p0)        
print( (1-sum(res[:1+n//2])) )

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
n=int(input())
P=np.array(list(map(float,input().split())))
DP=np.zeros(n+1)
DP[0]=1.0

for i in range(n):
  DP = np.roll(DP * P[i], 1) + DP * (1-P[i])
print(sum(DP[n//2+1:]))

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())
p = list(map(float, input().split()))

import numpy as np
dp = np.full(N+1, 0, dtype=np.float64)
dp[0] = 1
n_p = np.array(p)

for i in range(N):
    tmp      = np.zeros_like(dp)
    tmp[1:]  = dp[:-1] * n_p[i]
    tmp[:-1]+= dp[:-1] * (1-n_p[i])
    dp = tmp

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

# for i in range(1, 1+N): # timestep
#     for j in range(0, 0+i): # pos
#         dp[j] = dp[
#     # kdp[:i] a

# suml = [[1 for x in range(round+1)] for round in range(N+1)]
# 
# for e,p in enumerate(P):
#     for (es, s),_ in zip(enumerate(suml[e]), range(e+1)):
# 
#         if (es == 0):
#             suml[e+1][es]   = suml[e][es] * (1-p)
#         else:
#             suml[e+1][es]   += suml[e][es] * (1-p)
# 
#         suml[e+1][es+1] = suml[e][es] * p
# 
# 
# sumA = suml[N][:len(suml[N])//2-1:-1]
# sumA = sum(sumA)
# print(sumA)

Submission status: Accepted

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

"""
参考：https://qiita.com/drken/items/03c7db44ccd27820ea0d
・確率DP
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
pN = list(map(float, input().split()))

# dp[コインを投げた枚数][表が出た枚数] = そうなる確率
dp = [[0] * (N+1) for i in range(N+1)]
# 0枚投げて0になるのは100%
dp[0][0] = 1

for i in range(N):
    # 投げた枚数より表が多く出る訳ないのでi=jまで回せばOK
    for j in range(i+1):
        # 裏になる確率を下に送る
        dp[i+1][j] += dp[i][j] * (1-pN[i])
        # 表になる確率を右下に送る
        # 内ループは短く回るので添字オーバーは気にしなくていい
        dp[i+1][j+1] += dp[i][j] * (pN[i])

print('{:.10f}'.format(sum(dp[N][ceil(N, 2):])))

Submission status: Accepted

Solution code:
import sys

N=input()
P=map(float,  sys.stdin.readline().split() )

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


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

n=N/2+1

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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LF()
    r = [1]
    for i in range(n):
        t = [0] * (i+2)
        ai = a[i]
        a1 = 1 - a[i]
        for j in range(i+1):
            t[j] += r[j] * a1
            t[j+1] += r[j] * ai
        r = t

    return "{:0.10f}".format(sum(r[n//2+1:]))


print(main())

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
p = [float(i) for i in input().split()]
dp  = np.array([0.0] * (n + 1))
dp[0] = 1
for i in range(n):
 ura = dp*(1-p[i])
 ura[1:] += dp[:-1] * p[i]
 dp = ura

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from __future__ import division
import sys
raw_input = sys.stdin.readline
N = int(raw_input())
ans = [0 for x in range(N+1)]
ans[0] = 1
arr = map(float,raw_input().split())
for i in range(N):
    a = arr[i]
    for j in range(i+1,0,-1):
        ans[j] += ans[j-1]*a
        ans[j-1] *= (1-a)
res = 0
for i in range(int(N/2)+1,N+1):
    res += ans[i]
print res

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)

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

Submission status: Accepted

Solution code:
import numpy as np

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