Informatica Online Judge

  클릭 클릭 팡팡 (Hard) [1697 / 06A1]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 3   Total Tried : 5


The Champion of this Problem (C++) : ajou709 - ms / 317byte
My Best Submission (C++) : N/A

[koistudy.net (33rd 백인규)]

Background

열심히 오스를 하고 있는 인규를 보던 동현이는 "클릭클릭 팡팡"이라는 게임을 생각해 냈다.

게임은 총 $N$개의 버블을 박자에 맞춰 순서대로 터뜨리는 방식으로 진행된다.

정확한 박자에 버블을 터뜨리면 콤보가 $1$ 올라간다. 타이밍을 맞추지 못해 터뜨리는 데 실패한 경우, 지금까지의 콤보의 세제곱이 점수에 더해지고, 콤보 카운트는 $0$이 된다. 게임이 끝난 직후에도 콤보의 세제곱이 점수에 더해진다.

다시 말해, 각 버블의 성공/실패 결과를 나타내는 "O"와 "X"로 이루어진 길이 N인 문자열을 생각하고, 그 문자열에서 연속된 "O"들을 하나의 집합으로 묶으면, 각 집합의 크기의 세제곱의 합이 최종 점수가 된다.

동현이는 인규의 관심을 끌기 위해 다음과 같은 제안을 했다.

"네가 $i$번째 버블을 터뜨리는 데 성공할 확률이 $P_i$일 때, 너의 최종 점수의 기댓값을 구하면 그 값만큼 초코파이를 사 줄게!"

인규는 이것이 평생 초코파이를 먹을 수 있는 기회라는 것은 알았지만, 확률과 통계 시간에 부족한 잠을 보충했기 때문에 계산할 수 없었다. 따, 딱히 인규를 위해 하는 건 아니니까... 이번 한 번만 답을 대신 구해 주도록 하자.

Input

첫째 줄에는 버블의 수 $N$이 주어진다.

둘째 줄에는 $i$번째 버블을 터뜨리는 데 성공할 확률 $P_i$들이 실수로 주어진다.

[입력값의 정의역]

$1 ≤ N ≤ 200,000$
$1 ≤ i ≤ N$
$0 ≤ P_i ≤ 1$

Output

최종 점수의 기댓값을 소수점 이하 3자리까지 출력한다.

IO Example

입력1
3
0.5 0.5 0.5

출력1
6.000

입력2
4
0.1 0.2 0.3 0.4

출력2
2.603

설명
첫 번째 예제에서 게임의 결과는 총 8가지가 있으며, 확률은 모두 0.125로 같다. 각 결과의 점수를 모두 더하고 8로 나누면 점수의 기댓값은 6점임을 알 수 있다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]