| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 82 | 60 | 56 | 81.159% |
연세대학교는 다른 학교와 달리 수강신청을 할 때 마일리지 베팅 방식을 사용한다. 당신은 $N$개의 과목에 마일리지를 베팅해야 한다. 베팅 규칙은 다음과 같다.
그러나 마일리지를 얼마나 베팅해야 수강신청에 성공할 수 있을지는 정확히 알 수 없다. 따라서 당신은 인기도라는 개념을 도입하여 어떤 과목에 마일리지를 베팅했을 때 수강신청에 성공할 확률을 다음과 같이 추측했다.
이때 $A_i$는 $i$번째 과목의 인기도로, 그 과목을 100ドル\%$ 확률로 수강하기 위해 필요한 마일리지와 같다. 단, 인기가 매우 높아 $A_i\gt M$인 과목이 존재할 수 있음에 유의하라. 이 경우 최대치 $M$을 베팅해도 수강신청에 실패할 수 있다.
또한, 당신은 $i$번째 과목의 수강신청에 성공할 경우 $B_i$만큼, 실패할 경우 0ドル$만큼의 만족도를 얻는다. 이때, 만족도의 기댓값이 최대가 되는 마일리지 베팅 방법을 찾아보자.
첫째 줄에 과목의 수, 과목당 최대 마일리지, 총 마일리지를 나타내는 정수 $N,ドル $M,ドル $S$가 공백으로 구분되어 주어진다. (1ドル\leq N\leq 100,円 000,ドル 1ドル\leq M\leq 1,円 000,ドル $M\leq S\leq N\times M$)
둘째 줄에 $i$번째 과목의 인기도를 나타내는 $N$개의 정수 $A_i$가 공백으로 구분되어 주어진다. (1ドル\leq A_i\leq 1,円 000$)
셋째 줄에 $i$번째 과목을 수강했을 때의 만족도를 나타내는 $N$개의 정수 $B_i$가 공백으로 구분되어 주어진다. (1ドル\leq B_i\leq 1,円 000$)
$N$개의 정수 $X_1,X_2,\cdots ,X_N$를 공백으로 구분하여 출력한다. 이는 $i$번째 과목에 $X_i$ 마일리지를 베팅하는 것을 의미하며, 모든 $i$에 대해 0ドル\leq X_i\leq M$이고, $\sum_{i=1}^{N}{X_i}\leq S$를 만족한다.
기댓값이 최대가 되는 베팅 방법이 여러 가지일 경우, 그중 아무것이나 출력한다.
6 36 72 1 10 20 34 50 72 1 10 20 100 10 200
1 1 0 34 0 36
위와 같이 베팅할 경우 1ドル,ドル 4ドル$번째 과목은 $X_i=A_i$만큼의 마일리지를 베팅했으므로 반드시 수강신청에 성공할 수 있고, 3ドル,ドル 5ドル$번째 과목은 베팅을 하지 않았으므로 수강신청에 반드시 실패한다. 2ドル$번째 과목을 수강할 확률은 $\frac{1}{10}$이고, 6ドル$번째 과목을 수강할 확률은 $\frac{36}{72} =\frac{1}{2}$이다. 따라서 수강신청의 결과는 다음 4ドル$가지 경우가 존재한다.
| 수강하는 과목 | 확률 | 만족도 |
|---|---|---|
| $\{1,2,4,6\}$ | $\frac{1}{10}\times\frac{1}{2} =\frac{1}{20}$ | 1ドル+10+100+200=311$ |
| $\{1,4,6\}$ | $\frac{9}{10}\times\frac{1}{2} =\frac{9}{20}$ | 1ドル+100+200=301$ |
| $\{1,2,4\}$ | $\frac{1}{10}\times\frac{1}{2} =\frac{1}{20}$ | 1ドル+10+100=111$ |
| $\{1,4\}$ | $\frac{9}{10}\times\frac{1}{2} =\frac{9}{20}$ | 1ドル+100=101$ |
따라서, 이 베팅의 만족도의 기댓값은 $\frac{1}{20}\times 311+\frac{9}{20}\times 301+\frac{1}{20}\times 111+\frac{9}{20}\times 101=202$이다. 만족도의 기댓값이 202ドル$보다 높은 베팅 방법은 없음을 증명할 수 있다.
2 36 72 1 1 1000 1000
36 36
두 과목 모두 수강신청에 성공할 확률은 $\min(\frac{36}{1} ,1) =1$이다. 따라서 항상 1000ドル+1000=2000$의 만족도를 얻을 수 있다.
University > 연세대학교 > 2025 연세대학교 프로그래밍 경진대회 E번