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:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd

N = a_int()
P = list(map(float, readline().split()))

'''
dp[i,j]...表がちょうどj回出る確率、コイン[:i]を考慮したとき
dp[i+1,j]+=dp[i,j]*(1-P[i]) #配る、裏だった場合
dp[i+1,j+1]+= dp[i,j]*P[i] #表立った場合
'''
dp = [[0] * (N + 2) for _ in range(N + 2)]
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]  # 表立った場合

# 表がN//2+1以上回の確率を合計する
print(sum(dp[N][N // 2 + 1:]))
# print(*dp, sep='\n')

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[0][0]=[1,1]
dp=[[0]*(n+1) for _ in range(n+1)]
dp[0][0]=1
for t in range(1,n+1):
    dp[t][0]=dp[t-1][0]*(1-p[t-1])
    for h in range(1,t+1):
        dp[t][h]=dp[t-1][h-1]*p[t-1]+dp[t-1][h]*(1-p[t-1])
        #dp[t][h][1]=dp[t-1][h-1][1]*p[t-1] + dp[t-1][h][1]*(1-p[t-1])
        #dp[t][h][0]=dp[t-1][h-1][0]*(1-p[t-1]) + dp[t-1][h][0]*p[t-1]
ans=0
for h in range(t//2+1,n+1):
    ans+=dp[n][h]
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import deque

def main():
  N = int(input())
  arr = 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 k in range(i + 1):
      dp[i + 1][k + 1] += dp[i][k] * arr[i]
      dp[i + 1][k] += dp[i][k] * (1.0 - arr[i])
  
  ans = 0.0
  for i in range(N // 2 + 1, N + 1):
    ans += dp[N][i]
  
  print(ans)



if __name__ == "__main__":
  main()

Submission status: Accepted

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

dp=[[] for _ in range(N)]

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

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

Submission status: Accepted

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


def main():
    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):
        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+1, n+1):
        ans += dp[n][i]
            
    print(ans)
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# dp[i][j]=(i枚目のコインまで投げたとき、表がj枚でる確率)

# dp[i][j]=(i−1枚目のコインまで投げたとき、表がj枚でる確率)
# 								×(i枚目のコインが裏である確率)
# 		+(i−1枚目のコインまで投げたとき、表がj−1枚でる確率)
# 								×(i枚目のコインが表である確率)

N = int(input())
p = [0] + list(map(float, input().split()))
dp = [[0 for _ in range(N + 1)]for _ in range(N + 1)]
# print(dp)

# 0枚投げた時、表が0枚出る確率
dp[0][0] = 1

for i in range(1, N + 1):
    for j in range(0, i + 1):

        if j > 0:  # i枚目が裏の場合, i枚目が表の場合
            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])

ans = 0
# 条件を満たす表の数は、(N+1)//2, ..., N
for j in range((N + 1) // 2, N + 1):
    ans += dp[N][j]

print(ans)

Submission status: Accepted

Solution code:
import itertools
n = int(input())
p = list(map(float,input().split()))
p = [0] + p
#３回コインを投げて表が２回出る確率＝既に表が２回出ていて３回目に裏が出る確率＋既に表が１回出ていて３回目に表が出る確率
dp = [[0] * (n+1) for i in range(n+1)]
dp[1][0] = 1 - p[1]
dp[1][1] = p[1]
for i in range(1,n):
    for j in range(i+2):
        if j != 0:
            dp[i+1][j] = dp[i][j] * (1 - p[i+1]) + dp[i][j-1] * p[i+1]
        else:
            dp[i+1][j] = dp[i][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:
n = int(input())
P = list(map(float, input().split()))

memo = [[0] * (2 * n + 1) for _ in range(n+1)]
memo[0][n] = 1
for i in range(1, n+1):
    p = P[i-1]
    for j in range(2 * n + 1):
        if j == 0:
            memo[i][j] = (1-p) * memo[i-1][j+1]
        elif j == 2 * n:
            memo[i][j] = p * memo[i-1][j-1]
        else:
            memo[i][j] = p * memo[i-1][j-1] + (1-p) * memo[i-1][j+1]
ans = 0
for i in range(n+1, 2*n + 1):
    ans += memo[-1][i]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
def main():
    head_prob_table = [[0.0] * (N+1) for i in range(N)]
    head_prob = list(map(float, input().split()))

    head_prob_table[0][1] = head_prob[0]
    head_prob_table[0][0] = 1-head_prob[0]

    for i in range(1, N):
        for j in range(i+2):
            head_prob_table[i][j] += head_prob_table[i-1][j] * (1 - head_prob[i])
            if j > 0:
                head_prob_table[i][j] += head_prob_table[i-1][j-1] * head_prob[i]

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

if __name__ == '__main__':
    main()

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
# dp[X][I] := X回目の操作を終えてi回面が出る確率
for i in range(1, N+1):
    p = P[i-1]
    for j in range(i+1):
        if j >= 1:
            dp[i][j] = dp[i-1][j]*(1-p) + dp[i-1][j-1]*p
        else:
            dp[i][j] = dp[i-1][j]*(1-p)
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()))
dp = [[0]*(N+1) for i in range(N+1)]
dp[0][0] = 1
# dp[X][I] := X回目の操作を終えてi回面が出る確率
for i in range(1, N+1):
    p = P[i-1]
    for j in range(i+1):
        if j >= 1:
            dp[i][j] = dp[i-1][j]*(1-p) + dp[i-1][j-1]*p
        else:
            dp[i][j] = dp[i-1][j]*(1-p)
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 = [-1] + list(map(float, input().split()))
dp = [[1] * (N+1) for _ in range(N+1)] #i番目のコインまででj枚表が出る確率
dp[1][0] = 1 - p[1]
dp[1][1] = p[1]
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])
        elif j == i:
            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]
num = N // 2 + 1
ans = 0
while num <= N:
    ans += dp[N][num]
    num += 1
print(ans)

Submission status: Accepted

Solution code:
#BFSにdpを乗っける
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis=list(map(float,input().rstrip().split(" ")))
dp=[[0]*(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][0]=dp[i][0]*(1-lis[i])
        dp[i+1][j+1]=dp[i][j]*lis[i]+dp[i][j+1]*(1-lis[i])
#print(dp)
ans=0
for i in range((n+1)//2,n+1):
    ans+=dp[-1][i]
print(ans)

Submission status: Accepted

Solution code:


INF = float('inf')


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

    # dp = [[0] * (n + 1) for _ in range(n + 1)]
    # dp[0][0] = 1
    # # dp[i][j]: probability that out of the first
    # # i coins, j of them are heads
    # for i in range(1, n + 1):
    #     dp[i][0] = dp[i - 1][0] * (1 - p[i - 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 = sum(dp[n][n // 2 + 1:])
    # print(ans)

    dp = [0] * (n + 1)
    dp[0] = 1
    # dp[i]: probability of i heads so far
    for i, p_heads in enumerate(p):
        for j in reversed(range(1, i + 1 + 1)):
            dp[j] = dp[j - 1] * p_heads + dp[j] * (1 - p_heads)
        dp[0] *= 1 - p_heads

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


tc()

Submission status: Accepted

Solution code:


INF = float('inf')


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

    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    # dp[i][j]: probability that out of the first
    # i coins, j of them are heads
    for i in range(1, n + 1):
        dp[i][0] = dp[i - 1][0] * (1 - p[i - 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 = sum(dp[n][n // 2 + 1:])
    print(ans)


tc()

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

# N<=3000だから全探索は日が暮れる
# dp[i][j]:i枚目までのコインを投げて表がj回出る確率

dp=[[0 for j in range(N+1)] for i 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])
    # print(dp[i])
print(sum(dp[N-1][j] for j in range(N+1) if j > N//2))

Submission status: Accepted

Solution code:
import sys
from copy import copy

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(float, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N = in_n()
    p = in_nl()

    dp = [0] * (N + 1)
    dp[0] = 1 - p[0]
    dp[1] = p[0]

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def FI(): return list(map(float, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


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


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

Submission status: Accepted

Solution code:
# import numpy as np
n=int(input())
l=[0]+list(map(float,input().split()))
n+=1
dp=[[0 for i in range(n)]for i in range(n)]
dp[0][0]=1
for i in range(1,n):
    for j in range(i+1):
        if j==0:
            dp[i][j] = (1-l[i])*dp[i-1][j]
        else:
            dp[i][j]=(1-l[i])*(dp[i-1][j])+l[i]*dp[i-1][j-1]
ans=0
# print(np.array(dp))
for i in range((n)//2,n):
    ans+=dp[-1][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
for i in range(1,N+1):
	for j in range(N+1):
		if j<=i:
			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])
p=0
for i in range(N//2+1,N+1):
	p+=dp[-1][i]

print(p)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
P = [0]+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(1,N+1):
  for j in range(i+1):
    if j:
      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//2):]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
#sys.setrecursionlimit(200000000)
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
#def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])

    
def fun(A,N):
    dp = list2d(3000,3000,0)
    dp[0][0] = 1 - A[0]
    dp[0][1] = A[0]
    for i in range(1,N):
        for j in range(3000):
            #tails
            dp[i][j] += (1-A[i])*dp[i-1][j]
            #heads
            if j > 0:
                dp[i][j] += A[i]*(dp[i-1][j-1])
    ans = 0
    for i in range(N//2 + 1,3000):
        ans += dp[N-1][i]
    return ans
        
N = int(input())
A = list(map(float, input().split()))
print(fun(A,N))

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)

## a, bを無向辺として，隣接リストを作成
N = int(input())
p = [0] + list(map(float, input().split()))

m = N // 2 + 1

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

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

print(dp[N][m])

Submission status: Accepted

Solution code:
# Author: S Mahesh Raju
# Username: maheshraju2020
# Date: 01/07/2020

from sys import stdin, stdout, setrecursionlimit
from math import gcd, ceil, sqrt
from collections import Counter
from bisect import bisect_left, bisect_right
ii1 = lambda: int(stdin.readline().strip())
is1 = lambda: stdin.readline().strip()
iia = lambda: list(map(int, stdin.readline().strip().split()))
isa = lambda: stdin.readline().strip().split()
setrecursionlimit(100000)
mod = 1000000007

n = ii1()
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(1, n + 1):
    for j in range(i + 1):
        if j:
            dp[i][j] += dp[i - 1][j - 1] * p[i - 1]
        dp[i][j] += dp[i - 1][j] * (1 - p[i - 1])

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

Submission status: Accepted

Solution code:
def solve():
  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):
    for j in range(i+1):
      dp[i][j] = dp[i-1][j-1]*P[i-1]+dp[i-1][j]*(1-P[i-1])
  ans = sum(dp[-1][N//2+1:])
  return ans
print(solve())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
#import math
#import numpy as np
N = int(input())
#= input()
#= map(int, input().split())
p = list(map(float, input().split()))
#= [input(), input()]
#= [list(map(int, input().split())) for _ in range(N)]
#= {i:[] for i in range(N)}

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

dp[0][0] = 1

for i, p in enumerate(p, 1):
    pp = 1 - p
    dpi = dp[i - 1]
    for j in range(i + 1):     
        if j == 0:
            dp[i][j] = dpi[j] * pp
        elif j == i:
            dp[i][j] = dpi[j - 1] * p
        else:
            dp[i][j] = dpi[j - 1] * p + dpi[j] * pp


res = 0.0
n = N // 2 + 1

for cnt in dp[-1][n:]:
    res += cnt

print(res)

Submission status: Accepted

Solution code:
#import
#import math
#import numpy as np
N = int(input())
#= input()
#= map(int, input().split())
p = list(map(float, input().split()))
#= [input(), input()]
#= [list(map(int, input().split())) for _ in range(N)]
#= {i:[] for i in range(N)}

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

dp[0][0] = 1

for i, p in enumerate(p, 1):
    pp = 1 - p
    for j in range(i + 1):
        if j == 0:
            dp[i][j] = dp[i - 1][j] * pp
        elif j == i:
            dp[i][j] = dp[i - 1][j - 1] * p
        else:
            dp[i][j] = dp[i - 1][j - 1] * p + dp[i - 1][j] * pp

res = 0.0
n = N // 2 + 1

for cnt in dp[-1][n:]:
    res += cnt

print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jul 26 16:32:55 2020

@author: tinku
"""
n=int(input())
arr=list(map(float,input().split()))
dp=[[0 for j in range(n+1)] for i in range(n+1)]
dp[0][0]=1.0
for i in range(1,n+1):
    for j in range(n+1):
        if j==0:
            dp[i][j]=(1.0-arr[i-1])*dp[i-1][j]
        else:
            dp[i][j]=arr[i-1]*dp[i-1][j-1]+(1.0-arr[i-1])*dp[i-1][j]
print(sum(dp[n][n//2+1:]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin
n = int(stdin.readline())
p = list(map(float,stdin.readline().split()))
dp = [[0]*(n+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(n+1):
    for j in range(n+1):
        if i>j:
            continue
        dp[i][j] += (0 if i==0 or j==0 else dp[i-1][j-1]*p[j-1])
        dp[i][j] += (0 if j==0 else dp[i][j-1]*(1-p[j-1]))
x = (n+1)//2
ans = 0
while x != n+1:
    ans += dp[x][-1]
    x += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    naf = lambda: list(map(float, sys.stdin.readline().split()))

    n = ni()
    p = naf()

    dp = [[0 for _ in range(n + 1)] for __ in range(n + 1)]
    dp[0][0] = 1

    # dp[i][j] : pのうちi個めまでを投げて、表がj個出る確率
    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])

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
P = list(map(float,input().split()))
dp = [[0]*(n+1) for _ in range(n)]
dp[0][0] = 1-P[0]
dp[0][1] = 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])
        else:
            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())
dp = np.zeros(N+1, dtype=np.float64)
p_lst = list(map(float, input().split()))
dp[0] = 1
for p in p_lst:
  next_dp = dp * (1-p)
  next_dp[1:] += dp[:-1] * p
  dp = next_dp

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

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

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

Submission status: Accepted

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

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

D = [[0] * (n+1) for i in range(n+1)]
D[0][0] = 1
for i in range(1, n+1):
    for j in range(n+1):
        D[i][j] = D[i-1][j] * P[i-1]
        if j-1 >= 0:
            D[i][j] += D[i-1][j-1] * (1-P[i-1])

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

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

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

Submission status: Accepted

Solution code:
n=int(input())
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(1,n+1):
  for j in range(n+1):
  
          if j==0:
              dp[i][j]=dp[i-1][j]*(1.0-p[i-1])
          else:
              dp[i][j]=dp[i-1][j]*(1.0-p[i-1])+dp[i-1][j-1]*p[i-1]
       

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

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

Submission status: Accepted

Solution code:
import numpy as np
n= int(input())
ppp = list(map(float,input().split()))
dp = [0]*(n+1)
dp[0]=1
for p in ppp:
  ndp = [item*(1-p) for item in dp]
  ndp = [ndp[i] if i == 0 else ndp[i]+dp[i-1]*p for i in range(n+1)]
  dp = ndp
print(sum(dp[n//2+1:]))

Submission status: Accepted

Solution code:

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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:

n=int(input())
arr = list(map(float,input().split()))
dp = [[-1]*(n+1) for i in range(n+1)]
def func(n,x):
    for i in range(0,n+1):
        for j in range(0,n+1):
            if j==0:
                dp[i][j] = 1
            elif i==0:
                dp[i][j]=0
            else:
                p=(arr[i-1])*dp[i-1][j-1]
                q=(1-arr[i-1])*dp[i-1][j]
                dp[i][j] = p+q 
    
    return dp[n][x]

print("%0.10f"%func(n,(n+1)//2))

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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