시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 128 MB | 67 | 39 | 30 | 63.830% |
“영웅이여, 대 마상시합에 온 것을 환영합니다!” – 심판관 트루하트
쿠키런을 즐겨 플레이하는 샤바칸은 매일같이 하트가 충전되기를 기다리던 중, 한 TCG 장르의 게임을 접한다. 이 게임은 양 플레이어가 자신이 가진 카드 중 가장 좋은 30장을 순서대로 늘어놓아 자랑하며 경쟁하고, 여기서 번 골드를 이용해 새로운 카드를 구매하는 컨텐츠로 이루어져 있는데, 구입하는 새로운 카드는 무작위로 나타난다. 존재하는 카드의 등급은 다음과 같다.
열심히 골드를 모은 샤바칸은 N장의 카드를 구입하려고 한다. 샤바칸은 구입한 각 N장의 카드의 등급을 하나의 이진 문자열로 표현하고자 한다. 즉, 서로 다른 4^N가지의 등급 순열에 대해 각각 대응되는 이진 문자열이 존재해야 하며, 문자열의 끝을 명확히 알 수 있도록 이들 중 어떠한 문자열도 다른 문자열의 접두사(prefix)가 되어서는 안 된다.
구입한 카드에서 발생하는 등급의 확률분포가 주어질 때, 어떠한 N장의 등급 순열에서 이진 문자열로 변환하는 표현 방법에 대해, 우리는 샤바칸이 각 이진 문자열을 사용할 확률을 구할 수 있다. 이를 통해 우리는 샤바칸이 사용할 이진 문자열의 길이의 기댓값을 구할 수 있다.
구입한 카드에서 발생하는 등급의 확률분포가 주어질 때, 샤바칸이 사용할 이진 문자열의 길이의 기댓값의 최솟값을 구하시오.
입력의 첫 줄에는 구입하는 카드의 수 N (1 ≤ N ≤ 20)이 주어진다.
입력의 둘째 줄에는 구입한 카드에서 발생하는 일반 카드, 희귀 카드, 영웅 카드, 전설 카드의 확률 분포 PC, PR, PE, PL가 주어진다. 여기서 PC+PR+PE+PL=1임이 보장된다.
출력의 첫 줄에는 샤바칸이 사용할 이진 문자열의 길이의 기댓값의 최솟값을 출력한다.
절대 또는 상대 오차가 10-4이하인 경우 정답으로 인정된다
2 0.9 0.049999 0.05 0.000001
1.457510
20 0.25 0.25 0.25 0.25
40.000000