| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 27 | 9 | 9 | 52.941% |
KSA 학생인 종현이는 KSA의 가을 학교 축제에서 축제용 가상화폐 거래를 활성화하기 위해, 탐색 게임을 만들었다.
탐색 게임은, 게임을 시작할 때 사전에 정해진 정수 $X (1 \le X\le N)$의 값을 적절한 질문을 통해 맞히는 게임이다.
매 질문마다, 사용자는 서로 다른 $N$ 이하의 양의 정수를 $K$개 이하로 선택하여 입력한다.
게임이 종료될 때까지 위 과정이 반복된다. 게임 동안 $n$회 질문한 경우 최종 점수는 $(K+1)^{n-1}$점이 된다.
여러분은 게임에서 가상화폐를 벌어 종현이를 울리고 모든 간식과 기념품을 쓸어가고자 하는 해커다. 탐색 게임을 수행하여 얻는 점수의 기댓값을 최소화하는 전략을 찾아, 그 기댓값을 출력하자.
단, 정답 값인 $X$는 사용자 입력 이전에 정해지며, $X$가 $i$일 확률은 $\cfrac{P_i}{P_1 + \cdots + P_N}$이다.
첫 번째 줄에는 두 개의 정수 $N$, $K$가 공백으로 구분되어 주어진다.
두 번째 줄에는 $N$개의 정수 $P_1, P_2, \cdots, P_N$이 공백으로 구분되어 주어진다.
기댓값을 최소한으로 만드는 전략을 사용했을 때의 기댓값에 $(P_1 + P_2 + \cdots + P_N)$을 곱한 값을 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | $P_1 = P_2 = \cdots = P_N = 1$ |
| 2 | 10 | $N \leq 300$ |
| 3 | 85 | 추가 제약 조건 없음 |
5 1 1 1 1 1 1
13
5 2 1 1 1 1 1
11
4 1 4 3 2 10
39
4 1 4 3 2 12
42
School > 한국과학영재학교 > 2024 KSA Automata Winter Contest I번