| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 162 | 119 | 102 | 84.298% |
이번 MatKor Cup 예비소집에는 총 $N$명의 참가자가 참가하였으며, 대회장에는 $M$개의 자리가 준비되어 있다. 종우는 $N$명의 참가자들에게 각각 서로 다른 자리를 한 개씩 미리 배정해 두었고, 동우가 종우에게 어떻게 자리를 배정했는지 물어보았다.
종우는 그냥 알려줄 수는 없고, 동우에게 $N$명의 자리를 예측해 보라고 했다. 동우는 $M$개의 자리 중 서로 다른 $N$개의 자리를 고른 후, 각 참가자의 자리를 예측했다.
$N$명의 참가자 중 동우가 예측한 자리와 종우가 배정한 자리가 같은 사람의 수의 기댓값을 구해보자.
종우와 동우는 가능한 모든 경우에 대해 동일한 확률로 자리를 배정하거나 예측한다.
첫 번째 줄에 참가 인원과 자리의 개수 $N,M(1\le N\le M\le 10^{18})$이 공백으로 구분되어 주어진다.
첫 번째 줄에 $N$명의 참가자 중 동우가 예측한 자리와 종우가 배정한 자리가 같은 사람의 수의 기댓값을 출력한다.
기댓값을 기약분수 ${p\over q}(1 \le \lvert p\rvert$; $\ 2\le q$; $\gcd\left(\lvert p\rvert,q\right)=1)$로 약분해 $p$/$q$의 형태로 출력한다. 만약 답이 정수라면 예제와 같이 분모를 1ドル$로 생각한다.
주어진 조건 내에서 기댓값이 유리수임을 증명할 수 있다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 20 | $N=1$ |
| 2 | 30 | $N,M\le 8$ |
| 3 | 50 | 추가적인 제한 조건 없음 |
1 1
1/1
한 명이 참가하고, 자리가 한 개일 때는 반드시 1ドル$명의 자리를 맞추므로 기댓값은 1ドル$이다.
1 2
1/2
한 명이 참가하고, 자리가 두 개일 때는 $\frac{1}{2}$의 확률로 0ドル$명의 자리를 맞추고, $\frac{1}{2}$의 확률로 1ドル$명의 자리를 맞추므로 기댓값은 $\frac{1}{2}$이다.
2 2
1/1
참가자 두 명을 $A,ドル $B$라고 하면 종우는 $AB$혹은 $BA$로 자리를 배치했으며, 동우는 $AB$와 $BA$ 중 하나로 예측할 것이다. 즉, 총 2ドル\times 2=4$가지의 경우의 수 중 $\frac{2}{4}$의 확률로 0ドル$명의 자리를 맞추고, $\frac{2}{4}$의 확률로 2ドル$명의 자리를 맞추므로 기댓값은 $\frac{2}{4}\times 0 +\frac{2}{4}\times 2 = 1$이다.
2 4
1/2
총 12ドル\times 12=144$가지의 경우의 수 중 동우가 $\frac{84}{144}$의 확률로 0ドル$명의 자리를 맞추고, $\frac{48}{144}$의 확률로 1ドル$명의 자리를 맞추고, $\frac{12}{144}$의 확률로 2ドル$명의 자리를 맞추므로, 기댓값은 $\frac{84}{144}\times 0 +\frac{48}{144}\times 1 +\frac{12}{144}\times 2=\frac{1}{2}$이다.
123456789123456789 987654321987654321
13717421/109739369
University > 고려대학교 > MatKor Cup > 제5회 고려대학교 MatKor Cup: 2024 Summer/Fall 연습 세션 PB번