탐색 게임 | cho.sh

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)$을 곱한 값을 출력한다.