블랙 앤 화이트

시간 제한2초메모리 제한1024 MB

요약

각 아이가 흰색을 낼 확률이 주어질 때, 두 명만 남을 때까지 탈락 게임이 진행되는 라운드 수의 기댓값을 구한다.

난이도: 보통10점 중 7점
유형: 확률, 동적 계획법, 조합론, 수학
정답자: 아직 제출이 없습니다

문제

블랙 앤 화이트는 여러 라운드에 걸쳐 진행되는 중국의 어린이 놀이이다. 각 라운드에서 놀이에 참여하는 어린이들은 모두 손을 펴서("화이트") 내밀거나 손을 뒤집어("블랙") 내민다. 한 명만 다른 선택을 하고 나머지가 모두 같은 선택을 하면, 그 "튀는 아이"는 남은 게임에서 빠진다. 어린이가 두 명만 남을 때까지 놀이는 계속된다.

각 어린이는 자신만의 고정된 확률로 손을 펼지 여부를 독립적으로 선택한다. 이런 게임이 진행되는 라운드 수의 기댓값은 얼마인가?

입력

첫 번째 줄에는 어린이의 수를 나타내는 정수 $n$ ( $2 \le n \le 20$ )이 주어진다.

다음 $n$ 개의 줄 각각에는 실수 $p$ ( $0.1 \le p \le 0.9$ )가 하나씩 주어진다. 이는 각 어린이가 손을 펼 확률이다. 확률은 소수점 아래 세 자리 이하이다.

출력

라운드 수의 기댓값을 나타내는 실수 하나를 출력한다. 결과는 절대 오차 또는 상대 오차가 $10^{-6}$ 이내여야 한다.

예제3

예제 1
입력
```
3
0.5
0.5
0.5
```
예상 출력
```
1.3333333
```
예제 2
입력
```
3
0.3
0.3
0.3
```
예상 출력
```
1.5873015
```
예제 3
입력
```
5
0.1
0.3
0.5
0.7
0.9
```
예상 출력
```
7.4752846
```