탐색 게임

시간 제한2초메모리 제한1024 MB

요약

숨은 X를 찾기 위해 서로 다른 K개 이하의 수를 추측하고, 틀릴 때마다 추측값 중 X보다 작은 개수를 알려줄 때, 기대 점수를 최소로 만드는 전략의 값을 구한다.

문제

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