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:
n = int(input())
coin_list = [ float(v) for v in input().split() ]
probability_list = [1]

for i in coin_list:
    l = len(probability_list)
    new_probability_list = [0] * (l+2)
    for j in range(l):
        new_probability_list[j] += probability_list[j] * (1-i)
        new_probability_list[j+2] += probability_list[j] * i
    probability_list = new_probability_list

print(sum(probability_list[l//2+2:]))

Submission status: Accepted

Solution code:
def solve():
    p = read()
    result = think(p)
    write(result)


def read():
    n = read_int(1)[0]
    return read_float(n)


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_float(n):
    return list(map(lambda x: float(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(p):
    n = len(p)

    # dp[ith coin frip trial][faces count] = prob
    # dp[ith][facecount] = dp[ith - 1][facecount - 1] * Phead + dp[ith - 1][facecount] * Ptail

    accumulated = [[0.0 for x in range(n + 1)] for y in range(n)]
    accumulated[0][0] = 1.0 - p[0]
    accumulated[0][1] = p[0]

    for ith, each_p in enumerate(p):
        if ith == 0:
            continue
        for face_count in range(ith + 2):
            if face_count == 0:
                accumulated[ith][face_count] = accumulated[ith - 1][face_count] * (1.0 - each_p)
            elif face_count == ith + 1:
                accumulated[ith][face_count] = accumulated[ith - 1][face_count - 1] * each_p
            else:
                accumulated[ith][face_count] = accumulated[ith - 1][face_count] * (1.0 - each_p) + accumulated[ith - 1][face_count - 1] * each_p

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


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

dp = [[0] * (N * 2 + 3) for _ in range(2)]
def pos(i):
    return i + N + 1
dp[0][pos(0)] = 1
for i in range(1, len(ps) + 1):
    d = i % 2
    dm = (i - 1) % 2
    for j in range(-i, i + 1):
        dp[d][pos(j)] = dp[dm][pos(j-1)] * ps[i-1] + dp[dm][pos(j+1)] * (1.0 - ps[i-1])

s = 0
for i in range(1, N+1):
    s += dp[N%2][pos(i)]
print(s)

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
inputs = np.array([float(i) for i in input().split()])

dp = np.array([np.array([0.0 for _ in range(N+1)]) for _ in range(N+1)])
dp[1][0] = 1 - inputs[0]
dp[1][1] = inputs[0]
for i in range(2, N+1):
    dp[i][1:] = dp[i-1][1:] * (1.0 - inputs[i-1]) + dp[i-1][:N] * inputs[i-1]
    dp[i][0] = dp[i-1][0] * (1.0 - inputs[i-1])

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(float,input().split()))
b = [0]
table = [[0 for _ in range(n+1)]for  _ in range(n+1)]
table[0][0] = 1
for v in a:
    b.append(1-v)
s1 =1
s2 =1
ans = 0
a = [0]+a
for i in range(1,n+1):
    s1*=a[i]
    s2*=b[i]
    table[i][0]=s1
    table[0][i]=s2
for i in range(1,n):
    for j in range(1,n):
        if i+j<=n:
            table[i][j] = table[i-1][j]*a[i+j]+ table[i][j-1]*b[i+j]
for i in range(n+1):
    for j in range(n+1):
        if i>j and i+j ==n:
            ans+= table[i][j]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#dp8 #Coin

import sys
sys.setrecursionlimit(10000000)
def LI(): return list(map(float,sys.stdin.readline().split()))
def LIR(n): return [LI() for _ in range(n)]
mod = 10**9+7

def I():
    n = int(input())
    p = LI()
    #縦:コインの枚数,横:表が出た回数
    dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(1,n+1):
        for j in range(n+1):
            dp[i][j] = p[i-1]*dp[i-1][j-1]+(1-p[i-1])*dp[i-1][j]
    print(sum(dp[n][n//2+1:n+1]))





if __name__ == '__main__':
    I()

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N = inp()
pp = 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):
    p = pp[i-1]
    for n in range(N+1):
        if n == 0:
            dp[i][n] = dp[i-1][n]*(1-p)
        else:
            dp[i][n] = dp[i-1][n-1]*p + dp[i-1][n]*(1-p)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from __future__ import division, print_function
def main():
    n=int(input())
    l1=list(map(float,input().split()))
    dp=[ [0]*(n+1) for _ in range(n) ]
    dp[0][0]=l1[0]
    dp[0][1]=1-l1[0]
    for i in range(1,n):
        for j in range(i+2):
            if j>0:
                dp[i][j]=dp[i-1][j]*(l1[i])+dp[i-1][j-1]*(1-l1[i])
            else :
                dp[i][j]=dp[i-1][j]*(l1[i])
    if n%2==1:
        x=n//2
    else :
        x=n//2-1
    print(sum(dp[n-1][:x+1]))


######## Python 2 and 3 footer by Pajenegod and c1729

# Note because cf runs old PyPy3 version which doesn't have the sped up
# unicode strings, PyPy3 strings will many times be slower than pypy2.
# There is a way to get around this by using binary strings in PyPy3
# but its syntax is different which makes it kind of a mess to use.

# So on cf, use PyPy2 for best string performance.

py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
sys.setrecursionlimit(10**5)
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')


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

# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'

# Read all remaining integers in stdin, type is given by optional argument, this is fast
def readnumbers(zero = 0):
    conv = ord if py2 else lambda x:x
    A = []; numb = zero; sign = 1; i = 0; s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'0' [0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-' [0]: sign = -1
            elif s[i] != b'\r' [0]:
                A.append(sign*numb)
                numb = zero; sign = 1
            i += 1
    except:pass
    if s and s[-1] >= b'0' [0]:
        A.append(sign*numb)
    return A

if __name__== "__main__":
  main()

Submission status: Accepted

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

import functools
import operator
n = int(input())
p = list(map(float, input().split()))
half = n // 2 + 1

dp = [[None] * (n + 1) for _ in range(n + 1)]
# def dfs(n, depth=n - 1):
#     if depth < 0:
#         return 0
#
#     if dp[n][depth] is not None:
#         return dp[n][depth]
#
#     if n == 0:
#         r = functools.reduce(operator.mul, map(lambda x: 1 - x, p[:depth + 1]))
#     elif (n - 1) == depth:
#         r = functools.reduce(operator.mul, p[:depth + 1])
#     else:
#         r = dfs(n - 1, depth - 1) * p[depth] + dfs(n, depth - 1) * (1 - p[depth])
#     dp[n][depth] = r
#     return r
#
# print(sum(dfs(i) for i in range(half, n + 1)))

for i in range(0, n + 1):
    for depth in range(-1, n):
        if depth == -1:
            dp[i][depth] = 0
        elif i == 0:
            dp[i][depth] = functools.reduce(operator.mul, map(lambda x: 1 - x, p[:depth + 1]))
        elif (i - 1) == depth:
            dp[i][depth] = functools.reduce(operator.mul, p[:depth + 1])
        else:
            dp[i][depth] = dp[i - 1][depth - 1] * p[depth] + dp[i][depth - 1] * (1 - p[depth])

print(sum(dp[i][n - 1] for i in range(half, n + 1)))

Submission status: Accepted

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

import functools
import operator
n = int(input())
p = list(map(float, input().split()))
half = n // 2 + 1

dp = [[None] * (n + 1) for _ in range(n + 1)]
def dfs(n=half, depth=n - 1):
    if depth < 0 or (n - 1) > depth:
        return 0

    if dp[n][depth] is not None:
        return dp[n][depth]

    if n == 0:
        r = functools.reduce(operator.mul, map(lambda x: 1 - x, p[:depth + 1]))
    elif (n - 1) == depth:
        r = functools.reduce(operator.mul, p[:depth + 1])
    else:
        r = dfs(n - 1, depth - 1) * p[depth] + dfs(n, depth - 1) * (1 - p[depth])
    dp[n][depth] = r
    return r

print(sum(dfs(i) for i in range(half, n + 1)))

Submission status: Accepted

Solution code:
# @author 

import sys

class ICoins:
    def solve(self):
        n = int(input())
        p = [float(_) for _ in input().split()]
        dp = [0.0] * (n + 1)
        # dp[i][j] probability of having i heads after j tosses
        dp[0] = 1
        for j in range(1, n + 1):
            for i in range(j, 0, -1):
                dp[i] = dp[i] * (1 - p[j - 1]) + dp[i - 1] * p[j - 1]
            dp[0] = dp[0] * (1 - p[j - 1])
        ans = 0
        for i in range(n + 1):
            if i > n - i:
                ans += dp[i]
        print(ans)


solver = ICoins()
input = sys.stdin.readline

solver.solve()

Submission status: Accepted

Solution code:
# @author 

import sys

class ICoins:
    def solve(self):
        n = int(input())
        p = [float(_) for _ in input().split()]
        dp = [[0.0] * (n + 1) for _ in range(n + 1)]
        # dp[i][j] probability of having i heads after j tosses
        dp[0][0] = 1
        for j in range(1, n + 1):
            for i in range(j + 1):
                dp[i][j] = dp[i][j - 1] * (1 - p[j - 1])
                if i > 0:
                    dp[i][j] += dp[i - 1][j - 1] * p[j - 1]

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


solver = ICoins()
input = sys.stdin.readline

solver.solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N = int(input())
p = list(map(float, input().split()))
dp = [[0] * (N + 1) for _ in range(N)]
#dp[i][j]...i+1番目までのコインを投げて、j枚が表になる確率
dp[0][0] = 1 - p[0]
dp[0][1] = p[0]

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

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

Submission status: Accepted

Solution code:
n = int(raw_input())
a = list(map(float, raw_input().split()))
 
dp = [[0]*(n+1) for i in xrange(n+1)]
dp[0][0] = 1
 
for i in xrange(1,n+1):
  dp[0][i] = 0
  dp[i][0] = dp[i-1][0] * (1 - a[i-1])
  
for i in xrange(1, n+1):
  for j in xrange(1, n+1):
    dp[i][j] = dp[i-1][j-1] * a[i-1] + dp[i-1][j] * (1 - a[i-1])
ans = 0
for i in xrange(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]*(N+1) for _ in range(N+1)]
dp[0][0] = 1
for n in range(N+1):
    for m in range(N+1-n):
        dp[n][m] += p[n+m-1]*dp[n-1][m]+(1-p[n+m-1])*dp[n][m-1]

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

Submission status: Accepted

Solution code:
from subprocess import*
call(('pypy3','-c',"""
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:
input()
a=[1] 
for i in input().split():
  a=[x+(y-x)*float(i) for x,y in zip(a+[0],[0]+a)]
print(sum(a[len(a)//2:]))

Submission status: Accepted

Solution code:
import fileinput

def heads_win_proba(probs_list):
    prev_head_probs = [1.0]
    for coin_count, prob in enumerate(probs_list):
        coin_count += 1
        current_head_porbs = [0.0] * (coin_count + 1)
        for head_count in range(coin_count + 1):
            if head_count < coin_count:
                current_head_porbs[head_count] = prev_head_probs[head_count] * (1.0 - prob)
            if head_count > 0:
                current_head_porbs[head_count] += prev_head_probs[head_count - 1] * prob
        prev_head_probs = current_head_porbs
    return sum(prev_head_probs[len(prev_head_probs) // 2:])

inp = fileinput.FileInput()
coin_count = int(inp.readline())
prob_list = [float(n) for n in inp.readline().split(" ")]
print(heads_win_proba(prob_list))

Submission status: Accepted

Solution code:
# atcoder 動的計画法
# I Coins

import numpy as np


def get_inputs():
    # N コインの枚数
    # ps 各コインが表となる確率の配列(リスト)

    N = int(input())

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

    return N, ps


# 動的計画法の基づきテーブルを作成する
# dp[i][j] : i番目までのコインを投げた時に、j枚が表である確率
# 集める漸化式は下のようになる
# dp[i ][j ] = dp[i -1][j ]  *  (1 - p[i])  + dp[i - 1][j - 1] * p[i]
#
#

N, ps = get_inputs()

# dp = [[0.0] * (N + 1) for _ in range(N)]
dp = np.zeros((N, N + 1), dtype=float)

dp[0][1] = float(ps[0])
dp[0][0] = float(1.0 - ps[0])

for i in range(1, N):
    dp[i][:i + 2] = dp[i - 1][:i + 2] * (1 - ps[i])
    dp[i][1:i + 2] = dp[i - 1][:i + 1] * ps[i] + dp[i][1:i + 2]

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

Submission status: Accepted

Solution code:
n=int(input())
p=[float(i) for i in input().split()]
a=[1]
for d in p:
    a=[x*(1-d)+y*d for x,y in zip(a+[0],[0]+a)]
print(sum(a[n//2+1:]))

Submission status: Accepted

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

n = int(input())
f(n)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
P = map(float, input().split())
dp = Counter()
dp[0] = 1
for p in P:
    dp1 = Counter()
    for k, v in dp.copy().items():
        dp1[k] += v*(1 - p)
        dp1[k+1] += v*p 
    dp = dp1.copy()
print(sum(v for k, v in dp.items() if 2*k > N))

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
arr = list(map(float, input().split()))
dp = np.zeros(n + 1, dtype=float)
dp[0] = 1.0

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

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

Submission status: Accepted

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

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

dp = [[1 if k == 0 else 0 for k in range(N+1)] for _ in range(N+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[N][(N+1)//2])

Submission status: Accepted

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


def update(i, k):
    if k == 0:
        dp[i][k] = dp[i-1][0] * (1-P[i-1])
    elif k == i:
        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])


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

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

for i in range(1, N+1):
    for k in range(i+1):
        update(i, k)

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

Submission status: Accepted

Solution code:
n=int(input())
arr=list(map(float,input().split()))
dp=[0.0]*(n+1)
dp[0]=1.0
for i in range(n):
    p=arr[i]
    for j in range(i+1,-1,-1):
        if j==0:
            dp[j]=(1-p)*(dp[j])
        else:
            dp[j]=((p)*dp[j-1])+((1-p)*dp[j])
ans=0
for heads in range(n+1):
    tails=n-heads
    if heads>tails:
        ans+=dp[heads]
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def INT_(n): return int(n)-1


def MI(): return map(int, input().split())


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [input() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    N = I()
    p = LF()
    # dp[i][j]:=i枚目までで、k枚が表の確率
    dp = [[0] * (N+1) for _ in range(N)]
    dp[0][1] = p[0]
    dp[0][0] = 1-p[0]
    for i in range(1, N):
        for k in range(i+2):
            if k != 0:
                dp[i][k] += dp[i - 1][k - 1] * p[i]
            if k <= i:
                dp[i][k] += dp[i-1][k]*(1-p[i])
    ans = 0
    for i in range((N + 1) // 2, N + 1):
        ans += dp[N - 1][i]
    #print(*dp, sep="\n")
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

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

dp = [[0.0] * (len(v)+1) for i in range(len(v))]
for x in range(n):
	for a in range(x + 2):
		if x == 0 and a == 0:
			dp[x][a]=v[x]
		elif x == 0 and a == 1 and n != 1:
			dp[x][a]=1-v[x]
		elif a > n/2:
			dp[x][a]=dp[x-1][a]*v[x]
		else:
			dp[x][a]=dp[x-1][a]*v[x]+dp[x-1][a-1]*(1-v[x])
#import numpy
#print(numpy.matrix(dp));			
print(sum(dp[n-1]))

Submission status: Accepted

Solution code:
inp = lambda cast=int: list(map(cast, input().split()))
# printf = lambda s='', *args, **kwargs: print(str(s).format(*args), flush=True, **kwargs)
n, = inp()
A = [0.0] + inp(float)
dp = [[0.0 for _ in range(n + 1)] for _ in range(n + 1)]
res = 0.0
for i in range(n + 1):
    for j in range(n + 1):
        if i == 0:
            dp[i][j] = 1 if j == 0 else 0
        elif j == 0:
            dp[i][j] = dp[i-1][j] * (1 - A[i])
        else:
            dp[i][j] = dp[i-1][j] * (1 - A[i]) \
                       + dp[i-1][j-1] * A[i]
        if i == n and j > n/2:
            res += dp[i][j]
print(res)

Submission status: Accepted

Solution code:
n = int(input())
P = tuple(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(1,n+1):
    for j in range(i+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//2 + 1, n+1):
    res += dp[n][i]
print(res)

Submission status: Accepted

Solution code:
from itertools import accumulate
from math import*
from collections import deque
from collections import defaultdict
from itertools import permutations
from heapq import*
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import numpy as np

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

dp = np.zeros((N+2, N+1))

dp[1,0] = 1
for i in range(0, N):
    dp[1:(i+3), i+1] += dp[0:(i+2), i] * P[i]
    dp[1:(i+3), i+1] += dp[1:(i+3), i] * (1.0 - P[i])
        
print(sum(dp[-(N+1)//2:, -1]))

Submission status: Accepted

Solution code:
import numpy as np
from sys import stdin


def dp_solve(n):
    dp = np.zeros(n+1)
    dp[0] = 1
    pi = list(map(float, stdin.readline().split()))

    for i, p in enumerate(pi):
        dp[1:] = dp[1:]*(1-pi[i]) + dp[:n]*pi[i]
        dp[0] = dp[0]*(1-pi[i])
    return dp


if __name__ == "__main__":
    n = int(input())
    res = dp_solve(n)
    print(sum(res[n//2+1:]))

Submission status: Accepted

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

# 試行 x 表の回数
dp = [[0 for j in range(N + 1) ] for i in range(N + 1)]

# 0回目の試行は1
dp[0][0] = 1


for t_i in range(N):
    for o_i in range(N + 1):
        if dp[o_i][t_i] == 0:
            continue

        # 裏
        dp[o_i][t_i + 1] += dp[o_i][t_i] * (1-P[t_i])
        # 表
        dp[o_i + 1][t_i + 1] += dp[o_i][t_i] * P[t_i]


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

print(ans)

Submission status: Accepted

Solution code:
def func(num,arr):
  dp=[1]*(n+1)
  dp[0]=(1-arr[0])
  dp[1]=arr[0]
  for i in range(1,n):
    p0=arr[i]
    p1=1-arr[i]
    dp[i+1]=dp[i]*p0
    for j in range(1,i+1):
      dp[i+1-j]=dp[i-j]*p0+dp[i+1-j]*p1
    dp[0]=dp[0]*p1
  return dp

n=int(input())
arr=[float(s) for s in input().split()]
dp=func(n,arr)
ans=0
for i in range(int(n/2)+1,n+1):
  ans+=dp[i]
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

n=int(input())
ps=list(map(float,input().split()))
lim=(n+1)//2
dp=np.zeros(lim+1,dtype=np.float64)
dp[0]=1
for p in ps:
    dp[lim]=dp[lim]+dp[lim-1]*p
    dp[1:lim]=dp[:lim-1]*p+dp[1:lim]*(1-p)
    dp[0]=dp[0]*(1-p)
print(dp[-1])

Submission status: Accepted

Solution code:
n=int(input())
ps=list(map(float,input().split()))
lim=(n+1)//2
dp=[0]*(lim+1)
dp[0]=1
for pi,p in enumerate(ps):
    if pi+1>=lim:
        st=lim-1
        dp[lim]=dp[lim]+dp[lim-1]*p
    else:
        st=pi+1
    for i in range(st,0,-1):
        dp[i]=dp[i-1]*p+dp[i]*(1-p)
    dp[0]=dp[0]*(1-p)
print(dp[-1])

Submission status: Accepted

Solution code:
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, p in enumerate(P):
    for j in range(N + 1):
        dp[i + 1][j] += dp[i][j] * (1 - p)
        if j + 1 < N + 1:
            dp[i + 1][j + 1] += dp[i][j] * p

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

Submission status: Accepted

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


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

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

print(num)

Submission status: Accepted

Solution code:
N = int(input())
P = list(map(float, input().split()))
dp = [[0] * (N + 1) for i in range(N + 1)]
dp[0][0] = 1.0
for i in range(1, N + 1):
    for j in range(N):
        if j < N:
            dp[i][j + 1] += dp[i - 1][j] * P[i - 1]
        dp[i][j] += dp[i - 1][j] * (1 - P[i - 1])

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

print(num)

Submission status: Accepted

Solution code:
import sys

# input処理を高速化する
input = sys.stdin.readline

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

    # dp[j] := 表が j 枚となる確率
    # dp[j] = dp[j-1]*p[i] + dp[j]*(1-p[i]) ただしdp[j]が重複していることに注意
    dp = [0.0] * (N+1)
    # 初期条件
    dp[0]= 1.0

    for i in range(N):
        p_head = p[i]
        p_tail = 1 - p[i]
        dp = [dp[j -1] * p_head + dp[j] * p_tail for j in range(N+1)]
    
    ans = sum(dp[(N//2+1):])

    print(ans)

main()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline

def f2(n, p):
    dp = [ 0.0 ] * (n + 1)
    dp[0] = 1.0
    # pprint.pprint(dp, width = 50)
    for i in range(n):
        dp_ = list(dp)
        pi_ = 1 - p[i]
        for j in range(n + 1):
            dp[j] = dp_[j - 1] * p[i] + dp_[j] * pi_
        # pprint.pprint(dp, width = 50)
    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(f2(n, p))

Submission status: Accepted

Solution code:
#!/snap/bin/pypy3

import math

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

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

    for i, pr in enumerate(ps, start=1):
        for j in range(N+1):
            dp[i][j] = dp[i-1][j] * (1 - pr)
            if j:
                dp[i][j] += dp[i-1][j-1] * pr

    print(sum(dp[-1][math.ceil(N/2):]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

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

Submission status: Accepted

Solution code:
import sys
from sys import stdin
def input(): return sys.stdin.readline().strip()
import numpy as np

N = int(input())
pn = list(map(float,input().split()))
dp = np.array([0.0] * (N+1))
dp[0] = 1.0
for i in range(N):
    tmp = dp * (1-pn[i])
    tmp[1:] += dp[:-1] * pn[i]
    dp = tmp

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
P=tuple(map(float,input().split()))
DP=[[0.0]*(n+1) for _ in range(n+1)]
DP[0][0]=1.0
for i in range(1,n+1):
    for j in range(i+1):
        DP[i][j]=DP[i-1][j]*(1-P[i-1])
        if j:
            DP[i][j]+=DP[i-1][j-1]*P[i-1]
ans=0.0
for i in range(n//2+1,n+1):
    ans+=DP[-1][i]
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
P=tuple(map(float,input().split()))
DP=[[0]*(n+1) for _ in range(n+1)]
DP[0][0]=1
for i in range(1,n+1):
    for j in range(i+1):
        DP[i][j]=DP[i-1][j]*(1-P[i-1])
        if j:
            DP[i][j]+=DP[i-1][j-1]*P[i-1]
ans=0
for i in range(n//2+1,n+1):
    ans+=DP[-1][i]
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
P=tuple(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])
ans=0
for i in range(n//2+1,n+1):
    ans+=DP[-1][i]
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
P=tuple(map(float,input().split()))
DP=[[0]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    DP[i][0]=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[n][n//2+1])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
P=list(map(float,input().split()))
DP=[[0]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    DP[i][0]=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[n][n//2+1])