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

문제

스타트링크 은행은 고전적인 방식의 이자를 지급하는 대신에 복권 제도를 이용한 이자를 지급하고 있다. 이 제도는 은행에게 돈을 조금 더 적게 쓰게 만들어주지만, 대부분의 사람들은 그 차이를 눈치채지 못한다. 이 은행의 이자 시스템은 다음과 같이 이루어져 있다.

금요일 저녁에 은행은 계좌를 가지고 있는 사람들에게 잔고 1원당 티켓을 1개씩 지급한다. 모든 티켓을 지급한 후에는 티켓 하나를 랜덤하게 고른다. 모든 티켓이 당첨될 확률은 같다. 당첨된 사람의 계좌에 J원이 즉시 추가된다.

강호는 스타트링크 은행에 지금 막 계좌를 열고 나오는 길이다. 스타트링크 은행에 계좌를 가지고 있는 사람의 수와 잔고가 주어졌을 때, C주가 지난 후 강호의 통장 잔고의 기댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 50)이 주어진다. 

둘째 줄에는 스타트링크 은행에 통장 계좌를 가진 사람의 잔고가 주어진다. 첫 번째로 주어지는 잔고는 강호의 잔고이다. (0 ≤ 잔고 ≤ 100,000) 적어도 한 사람의 잔고는 0원보다 많다.

셋째 줄에는 J (1 ≤ J ≤ 1,000)가, 넷째 줄에는 C (1 ≤ C ≤ 1,000)가 주어진다.

출력

C주가 지난 후, 강호 잔고의 기댓값을 출력한다. 정답과의 절대/상대 오차는 10-9까지 허용한다.

예제 입력

2
100 100
100
2

예제 출력

200.0

예제 입력 2

3
2 2 2
1
2

예제 출력 2

2.6666666666666665

예제 입력 3

10
1 2 3 4 5 6 7 8 9 10
100
20

예제 출력 3

37.36363636363636

힌트

두 번째 예제의 경우에 첫 주가 지난 후 1/3의 확률로 (3, 2, 2)가, 1/3의 확률로 (2, 3, 2)가, 1/3의 확률로 (2, 2, 3)이 된다.

둘째 주에 (3, 2, 2)는 기댓값이 3.2486이 되고, (2, 3, 2)와 (2, 2, 3)은 기댓값이 2.2857이 된다. 따라서, 기댓값은 2.66667이다.

출처