시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)44312074.074%

문제

한별이가 블랙잭을 개조해 만든 슈퍼 블랙잭은 블랙잭보다 훨씬 다이나믹한 카드 게임이다. 한별이는 이 새로운 게임을 홍보하기 위해 $S$점 이상을 달성하는 사람에게 solved.ac 프로필 뱃지를 나눠주고 있다. 슈퍼 블랙잭의 규칙은 다음과 같다.

  • 카드 덱이 $D$개 있다. 각각의 덱에는 정수가 적힌 무한히 많은 카드가 뒷면이 보이게 놓여 있다.
  • $i$번째 덱 앞에는 정수 $A_i$가 적혀 있다. $A_i$가 적혀 있는 덱에서 카드를 한 장 뽑으면 $1$ 이상 $A_i$ 이하의 정수가 적힌 카드를 각각 $\frac{1}{A_i}$의 확률로 얻을 수 있다.
  • 플레이어는 원하는 덱을 하나 선택해 카드를 한 장 뽑아 가진다. 이 동작을 원하는 만큼 수행할 수 있으며, 매번 다른 덱을 선택해도 된다. 갖고 있는 카드에 적힌 수의 합이 플레이어의 점수가 된다.
  • 점수가 $E$ 초과가 되면 플레이어는 버스트당한다. 이렇게 되면 뽑은 카드를 전부 버리고 $0$점부터 다시 시작해야 한다.

수현이가 뱃지를 얻기 위해 무한히 버스트당하는 걸 지켜보던 준석이는 문득 뽑는 카드의 수가 최소가 되도록 최적의 전략으로 플레이할 경우 $S$점 이상을 달성하기 위해 뽑아야 하는 카드의 수의 기댓값이 궁금해졌다.

입력

첫 번째 줄에 덱의 개수 $D$가 주어진다. ($1 \le D \le 100$)

다음 줄에는 $D$개의 덱에 적힌 정수 $A_i$가 공백으로 구분되어 주어진다. ($1 \le A_i \le 10\,000$)

다음 줄에는 정수 $S$와 $E$가 공백으로 구분되어 주어진다. ($1 \le S \le E \le 10\,000$, 모든 $1 \le i \le D$에 대해 $A_i \le E$)

출력

슈퍼 블랙잭을 최적의 전략으로 플레이했을 때 뒤집어야 하는 카드의 수의 기댓값을 실수로 출력한다. 정답과의 절대/상대 오차가 $10^{-4}$ 이하라면 정답으로 인정된다.

예제 입력 1

1
5000
5000 10000

예제 출력 1

2.717466

예제 입력 2

4
1000 2000 3000 4000
10000 10000

예제 출력 2

3566.266360

예제 입력 3

13
1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 2100 2200
9900 10000

예제 출력 3

44.515395

출처

University > 서강대학교 > 2022 Sogang Programming Contest > Champion H번

University > 서강대학교 > 2022 Sogang Programming Contest > Champion (Open) H번

채점 및 기타 정보

  • 예제는 채점하지 않는다.