시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 12 11 11 91.667%

문제

N개의 동전이 탁자 위에 놓여져 있다. 동전은 모두 앞면이 위를 향하고 있다.

K개의 정수 A[i]가 주어진다. 가장 처음에 A[1]개의 동전을 랜덤하게 골라서 뒤집는다. 그 다음에는 A[2]개의 동전을 랜덤하게 골라서 뒤집는다. 이 과정을 계속해서 반복하고, 마지막에는 A[K]개의 동전을 랜덤하게 골라서 뒤집는다.

모든 과정을 완료했을 때, 앞면이 위를 향하는 동전 개수의 기댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 동전의 개수 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 K (1 ≤ K ≤ 50)이 주어진다. 셋째 줄에는 A[i] (1 ≤ A[i] ≤ N)가 주어진다.

출력

모든 과정을 완료한 후에 앞면이 위를 향하는 동전 개수의 기댓값을 출력한다.

정답과의 절대/상대 오차는 10-9까지 허용한다.

예제 입력

3
2
2 2

예제 출력

1.6666666666666667

예제 입력 2

10
3
10 10 10

예제 출력 2

0.0

예제 입력 3

10
6
2 7 1 8 2 8

예제 출력 3

4.792639999999999

힌트

예제 1의 경우에 첫 단계에서 동전 2개를 뒤집어야 한다. 두 번째 단계에는 다음과 같은 두 가지 상황이 가능하다.

  • 뒷면 2개를 골라서 뒤집는다. (확률: 1/3) 앞면의 개수는 3개가 된다.
  • 앞면 1개와 뒷면 1개를 골라서 뒤집는다. (확률: 2/3) 앞면의 개수는 1개가 된다.

기댓값은 1/3*3 + 2/3*1 = 5/3 이다.

출처