31540번 - 도박 문제 전문 상담은 국번없이 1336 서브태스크스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 74 | 45 | 35 | 62.500% |
문제
2024년 3월 9일 제4회 MatKor Cup이 개최된다. 이번 MatKor Cup에는 총 $n$명이 참가했고, 각 참가자는 $1$번부터 $n$번까지의 번호가 붙어있다.
이번 대회 운영진인 준혁이는 어떤 참가자가 우승할 지에 대해 자신을 제외한 운영진끼리 베팅을 하도록 했다. 베팅 결과 ‘$i$번 참가자가 우승한다’에 $a_i$원의 금액이 걸렸고, 총 $s=a_1+a_2+\cdots +a_n\ne 0$원의 금액이 걸렸다. 실제로 $i$번째 사람이 우승할 확률은 베팅 금액에 비례하는 $\frac{a_i}{s}$이다. 우승자는 반드시 한 명이다.
도박을 싫어해 베팅에 참여하지 않은 종우는 자신이 공평하게 배당을 나눌 수 있다고 말했다. 그 결과, 종우가 배당을 정하기로 했다.
$i$번 참가자의 배당이 $b_i$라고 할 때, 배당 상수 $m$과 $t$에 대해 배당의 총합이 $t=b_1^m+b_2^m+\cdots +b_n^m$가 되도록 $b_i$들을 정하고자 한다. 이때 두 배당 상수는 양의 정수이고, 각 참가자의 배당은 음이 아닌 실수이다.
만약 $k$번 참가자가 우승한다면, 준혁이는 $k$번 참가자에 베팅한 사람들이 건 돈의 $b_k$배를 각각 배당금으로 지급한다. 즉, $k$번 참가자가 우승할 경우 받은 $s$원에서 $a_kb_k$원을 배당금으로 지급하므로, 초기에 비해 $s-a_kb_k$원을 벌게 된다. 만약 이 값이 음수라면, 그 절댓값만큼의 돈을 잃게 된다.
종우는 준혁이가 도박 운영을 통해 돈을 버는 것을 못마땅하게 생각해 준혁이가 최대한 돈을 벌지 못하게 하고 싶다. 참가자별로 걸린 금액과 배당 상수가 주어질 때 종우를 도와 준혁이가 버는 금액의 기댓값이 최소가 되도록 배당을 조정해 보자.
입력
첫 번째 줄에 대회 참가자의 수 $n$, 배당의 총합을 결정할 정수 상수 $m$, $t$가 공백으로 구분되어 주어진다. $(1\le n, m, t\le 10^6)$
두 번째 줄에 베팅 결과 각 참가자에게 걸린 금액을 나타내는 $n$개의 정수 $a_i$가 공백으로 구분되어 주어진다. $(0\le a_i\le 1\,000)$
주어지는 입력은 $s> 0$을 만족한다.
출력
준혁이가 버는 금액의 기댓값의 최솟값을 출력한다. 이 값이 음수일 수 있음에 유의하자.
정답과의 절대오차 또는 상대오차가 $10^{-6}$ 이하이면 정답으로 인정된다.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 8 | $n = 1$ |
| 2 | 95 | $n = 2$ |
| 3 | 27 | $m = 1$ |
| 4 | 62 | $m = 2$ |
| 5 | 108 | 추가적인 제한 조건 없음 |
예제 입력 1
1 1 1 10
예제 출력 1
0
$1= b_1^1$ 이므로, $b_1=1$이다.
- $1$번 참가자가 우승할 확률은 $1$이고, $1$번 참가자가 우승하면 $10-10\cdot 1 = 0$원을 번다.
따라서 준혁이가 버는 금액의 기댓값은 $1\cdot 0 = 0$이고, 이것이 최소이다.
예제 입력 2
2 2 2 1 1
예제 출력 2
1
$2= b_1^2+b_2^2$ 을 만족하도록 $b_1=1$, $b_2=1$로 정할 수 있다.
- $1$번 참가자가 우승할 확률은 $\frac{1}{2}$이고, $1$번 참가자가 우승하면 $2-1\cdot 1 = 1$원을 번다.
- $2$번 참가자가 우승할 확률은 $\frac{1}{2}$이고, $2$번 참가자가 우승하면 $2-1\cdot 1 = 1$원을 번다.
따라서 준혁이가 버는 금액의 기댓값은 $\frac{1}{2}\cdot 1 +\frac{1}{2}\cdot 1= 1$이고, 이것이 최소이다.
예제 입력 3
2 2 2 0 10
예제 출력 3
-4.1421356237
$2= b_1^2+b_2^2$ 을 만족하도록 $b_1=0$, $b_2=\sqrt{2}$로 정할 수 있다.
- $1$번 참가자가 우승할 확률은 $\frac{0}{10}=0$이고, $1$번 참가자가 우승하면 $10-0\cdot 0 = 10$원을 번다.
- $2$번 참가자가 우승할 확률은 $\frac{10}{10}=1$이고, $2$번 참가자가 우승하면 $10-10\cdot\sqrt{2} = 10-10\sqrt{2}$원을 번다.
따라서 준혁이가 버는 금액의 기댓값은 $0\cdot 10 +1\cdot \left(10-10\sqrt{2}\right)= 10-10\sqrt{2}$이고, 이것이 최소이다.
예제 입력 4
2 1 3 4 5
예제 출력 4
0.6666666667
$3= b_1^1+b_2^1$ 을 만족하도록 $b_1=0$, $b_2=3$으로 정할 수 있다.
- $1$번 참가자가 우승할 확률은 $\frac{4}{9}$이고, $1$번 참가자가 우승하면 $9-4\cdot 0 = 9$원을 번다.
- $2$번 참가자가 우승할 확률은 $\frac{5}{9}$이고, $2$번 참가자가 우승하면 $9-5\cdot 3 = -6$원을 번다.
따라서 준혁이가 버는 금액의 기댓값은 $\frac{4}{9} \cdot 9 +\frac{5}{9}\cdot \left(-6\right)= \frac{2}{3}$이고, 이것이 최소이다.
예제 입력 5
2 2 6 1 1
예제 출력 5
0.2679491924
$6= b_1^2+b_2^2$ 을 만족하도록 $b_1=\sqrt{3}$, $b_2=\sqrt{3}$로 정할 수 있다.
- $1$번 참가자가 우승할 확률은 $\frac{1}{2}$이고, $1$번 참가자가 우승하면 $2-1\cdot \sqrt{3} = 2-\sqrt{3}$원을 번다.
- $2$번 참가자가 우승할 확률은 $\frac{1}{2}$이고, $2$번 참가자가 우승하면 $2-1\cdot \sqrt{3} = 2-\sqrt{3}$원을 번다.
따라서 준혁이가 버는 금액의 기댓값은 $\frac{1}{2} \cdot \left(2-\sqrt{3}\right) +\frac{1}{2} \cdot \left(2-\sqrt{3}\right)= 2-\sqrt{3}$이고, 이것이 최소이다.
예제 입력 6
4 3 123456 999 987 975 951
예제 출력 6
-26785.85891
출처
University > 고려대학교 > MatKor Cup > 제4회 고려대학교 MatKor Cup: 2024 Winter/Spring H번
- 문제를 만든 사람: chlwnsgurb, kidw0124, yijw0930
- 문제를 번역한 사람: tikiliki0417
- 문제를 검수한 사람: devluyten, lighter, sshs29hanul, tlsdydaud1, utilforever, w8385
채점 및 기타 정보
- 예제는 채점하지 않는다.