Educational DP Contest - Coins

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}.

Examples

Input

3
0.30 0.60 0.80


Output

0.612


Input

1
0.50


Output

0.5


Input

5
0.42 0.01 0.42 0.99 0.42


Output

0.3821815872

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


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


N = int(input())
P = list(map(float, input().split()))
ans = [[0 for e in range(2 * N + 3)] for f in range(N + 1)]
ans[0][N + 1] = 1
for n in range(1, N + 1):
	for i in range(N + 1 - n, N + 2 + n):
		ans[n][i] = ans[n - 1][i - 1] * P[n - 1] + ans[n - 1][i + 1] * (1 - P[n - 1])
t = 0
for i in range(N + 1, 2 * N + 3):
	t += ans[N][i]
print(t)


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

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


N = int(input())
P = [float(i) for i in input().split()]
dp = [0.0] * (N + 1)
dp[0] = 1.0
for (i, p) in enumerate(P, 1):
	dp = [p * a + (1 - p) * b for (a, b) in zip([0] + dp, dp)]
print(sum(dp[-(-N // 2):]))


import sys
input = sys.stdin.readline
N = int(input())
prob_table = list(map(float, input().split()))
dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
dp[0][0] = 1
for i in range(0, N):
	for j in range(i + 1):
		dp[i + 1][j + 1] += dp[i][j] * prob_table[i]
		dp[i + 1][j] += dp[i][j] * (1 - prob_table[i])
print(sum(dp[N][N // 2 + 1:]))


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


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


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


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


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


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


n = int(input())
p = [float(i) for i in 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):
		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[n][i]
print(ans)


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


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)


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


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


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


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


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


(N,) = map(int, input().split())
Ps = map(float, input().split())
dp = [0] * (N + 1) ** 2
dp[0] = 1
for (i, p) in enumerate(Ps):
	for j in range(N + 1):
		dp[(i + 1) * (N + 1) + j] = p * dp[i * (N + 1) + j - 1] + (1 - p) * dp[i * (N + 1) + j]
r = 0
for i in range(N, N // 2, -1):
	r += dp[N * (N + 1) + i]
print(r)


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


N = int(input())
ps = map(float, input().split())
dp = [0] * (N + 1)
dp[0] = 1
for p in ps:
	pp = 1 - p
	for j in reversed(range(N + 1)):
		dp[j] = dp[j] * pp + dp[j - 1] * p
print(sum(dp[(N + 1) // 2:]))


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


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


N = int(input())
P = [float(i) for i in input().split()]
dp = [[0] * (N + 1) for i in range(N + 1)]
dp[0][0] = 1
for n in range(1, N + 1):
	dp[n][0] = dp[n - 1][0] * (1 - P[n - 1])
	for j in range(1, n + 1):
		dp[n][j] = dp[n - 1][j] * (1 - P[n - 1]) + dp[n - 1][j - 1] * P[n - 1]
m = N // 2
ans = 0
for i in range(m + 1, N + 1):
	ans += dp[N][i]
print(ans)


N = int(input())
p = list(map(lambda x: float(x), input().split()))
dp = [[0] * (N + 1) for i in range(N)]
dp[0][0] = 1 - p[0]
dp[0][1] = p[0]
for i in range(1, N):
	for h in range(N + 1):
		dp[i][h] = dp[i - 1][h] * (1 - p[i]) + (0 if h == 0 else dp[i - 1][h - 1] * p[i])
print(sum(dp[N - 1][int((N + 1) / 2):]))


N = int(input())
p = [float(i) for i in input().split()]
dp = [[0] * (N + 1) for i in range(N + 1)]
dp[0][0] = 1
for i in range(N):
	dp[i + 1][0] = dp[i][0] * (1 - p[i])
	for j in range(i + 1):
		dp[i + 1][j + 1] = dp[i][j] * p[i] + dp[i][j + 1] * (1 - p[i])
print(sum(dp[N][N // 2 + 1:]))


N = int(input())
(*P,) = map(float, input().split())
dp = [[0] * (N + 1) for i in range(N + 1)]
for i in range(N + 1):
	if N <= 2 * i:
		dp[N][i] = 1.0
for c in range(N - 1, -1, -1):
	p = P[c]
	for k in range(N - 1, -1, -1):
		dp[c][k] = r = p * dp[c + 1][k + 1] + (1.0 - p) * dp[c + 1][k]
print('%.10f' % dp[0][0])


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


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


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


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(N):
	for head in range(N):
		dp[i + 1][head + 1] += dp[i][head] * P[i]
		dp[i + 1][head] += dp[i][head] * (1 - P[i])
print(sum(dp[-1][(N + 1) // 2:]))


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


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


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


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


N = int(input())
P = [float(a) for a in input().split()]
pre = []
post = [1]
for i in range(N):
	pre = post
	post = [0] * (i + 2)
	for j in range(i + 2):
		if j > 0:
			post[j] += pre[j - 1] * P[i]
		if j <= i:
			post[j] += pre[j] * (1 - P[i])
print(sum(post[N // 2 + 1:]))


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


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


N = int(input())
inp = list(map(lambda x: float(x), input().split(' ')))
dp = [[0] * (N + 1) for i 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 - inp[i])
		dp[i + 1][j + 1] += dp[i][j] * inp[i]
print(sum(dp[N][N // 2 + 1:N + 1]))


n = input()
n = int(n)
p = list(map(float, input().split()))
l = [1]
for i in range(n):
	t1 = [j * (1 - p[i]) for j in l]
	t1.append(0)
	t2 = [0] + [j * p[i] for j in l]
	l = [t1[j] + t2[j] for j in range(len(t1))]
l.reverse()
print(sum([l[i] for i in range((n + 1) // 2)]))


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[i + 1][j] += dp[i][j] * (1 - p[i])
		dp[i + 1][j + 1] += dp[i][j] * p[i]
		if j == i:
			break
print(1.0 - sum(dp[-1][:N // 2 + 1]))


n = int(input())
P = [float(i) for i in input().split()]
DP = [[0] * (n + 1) for j in range(n + 1)]
DP[0][0] = 1
for i in range(n):
	for j in range(n):
		DP[i + 1][j + 1] += DP[i][j] * P[i]
		DP[i + 1][j] += DP[i][j] * (1 - P[i])
print(sum(DP[n][(n + 1) // 2:]))


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


N = int(input())
p = [float(x) for x in input().split()]
dp = [[0 for x in range(N + 1)] for n in range(N + 1)]
dp[0][0] = 1
for i in range(N):
	for x in range(N):
		dp[i + 1][x + 1] += dp[i][x] * p[i]
		dp[i + 1][x] += dp[i][x] * (1 - p[i])
print(sum(dp[N][N // 2 + 1:]))


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


def main():
	n = int(input())
	p = [float(i) for i in input().split()]
	dp = [[0] * (n + 1) for i in range(n + 1)]
	dp[0][0] = 1
	for i in range(n):
		dp[i + 1][0] = dp[i][0] * (1 - p[i])
		for j in range(i + 1):
			dp[i + 1][j + 1] = dp[i][j] * p[i] + dp[i][j + 1] * (1 - p[i])
	print(sum(dp[n][(n + 1) // 2:]))
main()


n = int(input())
p = tuple(map(float, input().split()))
dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1
for (i, prob) in enumerate(p, 1):
	for j in range(i + 1):
		dp[i][j] = dp[i - 1][j] * prob + dp[i - 1][j - 1] * (1 - prob)
res = sum((dp[n][j] for j in range(n // 2 + 1)))
print(res)


n = int(input())
l = list(map(float, input().split()))
k = [0] * (n + 1)
k[0] = 1
for p in l:
	for j in range(n, -1, -1):
		k[j] *= 1 - p
		if j != 0:
			k[j] += k[j - 1] * p
print(sum(k[n // 2 + 1:]))


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


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


N = int(input())
p = [float(x) for x in input().split()]
dp = [[0 for j in range(N + 5)] for i in range(N + 5)]
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])
M = (N + 1) // 2
result = 0
for i in range(M, N + 1):
	result += dp[N][i]
print(result)


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


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):
	p = P[i]
	for j in range(i + 1):
		dp[i + 1][j + 1] += dp[i][j] * p
		dp[i + 1][j] += dp[i][j] * (1 - p)
ans = sum((dp[N][i] for i in range(N // 2 + 1, N + 1)))
print('{:.10f}'.format(ans))


N = int(input())
P = list(map(float, input().split()))
NOW = [1]
for i in range(N):
	NEXT = [0] * (i + 2)
	for j in range(i + 1):
		NEXT[j] += NOW[j] * (1 - P[i])
		NEXT[j + 1] += NOW[j] * P[i]
	NOW = NEXT
print(sum(NOW[1 + N // 2:]))


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


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