문제
KSA 학생인 종현이는 KSA의 가을 학교 축제에서 축제용 가상화폐 거래를 활성화하기 위해, 탐색 게임을 만들었다.
탐색 게임은, 게임을 시작할 때 사전에 정해진 정수 $X (1 \le X\le N)$의 값을 적절한 질문을 통해 맞히는 게임이다.
매 질문마다, 사용자는 서로 다른 $N$ 이하의 양의 정수를 $K$개 이하로 선택하여 입력한다.
- 입력한 값 중에 $X$가 있는 경우, 게임이 종료된다.
- 그렇지 않은 경우, 방금 입력한 정수 중 $X$보다 작은 것의 개수가 사용자에게 주어진다.
게임이 종료될 때까지 위 과정이 반복된다. 게임 동안 $n$회 질문한 경우 최종 점수는 $(K+1)^{n-1}$점이 된다.
여러분은 게임에서 가상화폐를 벌어 종현이를 울리고 모든 간식과 기념품을 쓸어가고자 하는 해커다. 탐색 게임을 수행하여 얻는 점수의 기댓값을 최소화하는 전략을 찾아, 그 기댓값을 출력하자.
단, 정답 값인 $X$는 사용자 입력 이전에 정해지며, $X$가 $i$일 확률은 $\cfrac{P_i}{P_1 + \cdots + P_N}$이다.
출력
기댓값을 최소한으로 만드는 전략을 사용했을 때의 기댓값에 $(P_1 + P_2 + \cdots + P_N)$을 곱한 값을 출력한다.
제한
- 1ドル\leq N\leq 1500$
- 1ドル\leq K \leq 5$
- 1ドル\leq P_i\leq 1000$
서브태스크
| 번호 | 배점 | 제한 | | 1 | 5 | $P_1 = P_2 = \cdots = P_N = 1$
|
| 2 | 10 | $N \leq 300$
|
| 3 | 85 | 추가 제약 조건 없음
|
W3sicHJvYmxlbV9pZCI6IjMxNDQxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkMGQwXHVjMGM5IFx1YWM4Y1x1Yzc4NCIsImRlc2NyaXB0aW9uIjoiPHA+S1NBIFx1ZDU1OVx1YzBkZFx1Yzc3OCBcdWM4ODVcdWQ2MDRcdWM3NzRcdWIyOTQgS1NBXHVjNzU4IFx1YWMwMFx1Yzc0NCBcdWQ1NTlcdWFkNTAgXHVjZDk1XHVjODFjXHVjNWQwXHVjMTFjIFx1Y2Q5NVx1YzgxY1x1YzZhOSBcdWFjMDBcdWMwYzFcdWQ2NTRcdWQzZDAgXHVhYzcwXHViNzk4XHViOTdjIFx1ZDY1Y1x1YzEzMVx1ZDY1NFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQsIDxzdHJvbmc+XHVkMGQwXHVjMGM5IFx1YWM4Y1x1Yzc4NDxcL3N0cm9uZz5cdWM3NDQgXHViOWNjXHViNGU0XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQwZDBcdWMwYzkgXHVhYzhjXHVjNzg0XHVjNzQwLCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTYwIFx1YjU0YyBcdWMwYWNcdWM4MDRcdWM1ZDAgXHVjODE1XHVkNTc0XHVjOWM0IFx1YzgxNVx1YzIxOCAkWCAoMSBcXGxlIFhcXGxlIE4pJFx1Yzc1OCBcdWFjMTJcdWM3NDQgXHVjODAxXHVjODA4XHVkNTVjIFx1YzljOFx1YmIzOFx1Yzc0NCBcdWQxYjVcdWQ1NzQgXHViOWRlXHVkNzg4XHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWU0IFx1YzljOFx1YmIzOFx1YjljOFx1YjJlNCwgXHVjMGFjXHVjNmE5XHVjNzkwXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggJE4kIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHViOTdjICRLJFx1YWMxYyBcdWM3NzRcdWQ1NThcdWI4NWMgXHVjMTIwXHVkMGRkXHVkNTU4XHVjNWVjIFx1Yzc4NVx1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWM3ODVcdWI4MjVcdWQ1NWMgXHVhYzEyIFx1YzkxMVx1YzVkMCAkWCRcdWFjMDAgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMCwgXHVhYzhjXHVjNzg0XHVjNzc0IFx1Yzg4NVx1YjhjY1x1YjQxY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWFjYmRcdWM2YjAsIFx1YmMyOVx1YWUwOCBcdWM3ODVcdWI4MjVcdWQ1NWMgXHVjODE1XHVjMjE4IFx1YzkxMSAkWCRcdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIFx1YWM4M1x1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjMGFjXHVjNmE5XHVjNzkwXHVjNWQwXHVhYzhjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWFjOGNcdWM3ODRcdWM3NzQgXHVjODg1XHViOGNjXHViNDIwIFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWM3MDQgXHVhY2ZjXHVjODE1XHVjNzc0IFx1YmMxOFx1YmNmNVx1YjQxY1x1YjJlNC4gXHVhYzhjXHVjNzg0IFx1YjNkOVx1YzU0OCAkbiRcdWQ2OGMgXHVjOWM4XHViYjM4XHVkNTVjIFx1YWNiZFx1YzZiMCBcdWNkNWNcdWM4ODUgXHVjODEwXHVjMjE4XHViMjk0ICQoSysxKV57bi0xfSRcdWM4MTBcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1ZWNcdWI3ZWNcdWJkODRcdWM3NDAgXHVhYzhjXHVjNzg0XHVjNWQwXHVjMTFjIFx1YWMwMFx1YzBjMVx1ZDY1NFx1ZDNkMFx1Yjk3YyBcdWJjOGNcdWM1YjQgXHVjODg1XHVkNjA0XHVjNzc0XHViOTdjIFx1YzZiOFx1YjlhY1x1YWNlMCBcdWJhYThcdWI0ZTAgXHVhYzA0XHVjMmRkXHVhY2ZjIFx1YWUzMFx1YjE1MFx1ZDQ4OFx1Yzc0NCBcdWM0ZjhcdWM1YjRcdWFjMDBcdWFjZTBcdWM3OTAgXHVkNTU4XHViMjk0IFx1ZDU3NFx1Y2VlNFx1YjJlNC4gXHVkMGQwXHVjMGM5IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NThcdWM1ZWMgXHVjNWJiXHViMjk0IFx1YzgxMFx1YzIxOFx1Yzc1OCBcdWFlMzBcdWIzMTNcdWFjMTJcdWM3NDQgPHN0cm9uZz5cdWNkNWNcdWMxOGNcdWQ2NTQ8XC9zdHJvbmc+XHVkNTU4XHViMjk0IFx1YzgwNFx1YjdiNVx1Yzc0NCBcdWNjM2VcdWM1NDQsIFx1YWRmOCBcdWFlMzBcdWIzMTNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHVjNzkwLjxcL3A+XHJcblxyXG48cD48c3Ryb25nPlx1YjJlOCwgXHVjODE1XHViMmY1IFx1YWMxMlx1Yzc3OCAkWCRcdWIyOTQgXHVjMGFjXHVjNmE5XHVjNzkwIFx1Yzc4NVx1YjgyNSBcdWM3NzRcdWM4MDRcdWM1ZDAgXHVjODE1XHVkNTc0XHVjOWMwXHViYTcwLCAkWCRcdWFjMDAgJGkkXHVjNzdjIFx1ZDY1NVx1Yjk2MFx1Yzc0MCAkXFxjZnJhY3tQX2l9e1BfMSArIFxcY2RvdHMgKyBQX059JFx1Yzc3NFx1YjJlNC48XC9zdHJvbmc+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCAkTiQsICRLJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgJE4kXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCAkUF8xLCBQXzIsIFxcY2RvdHMsIFBfTiRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhZTMwXHViMzEzXHVhYzEyXHVjNzQ0IFx1Y2Q1Y1x1YzE4Y1x1ZDU1Y1x1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVjODA0XHViN2I1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU4OFx1Yzc0NCBcdWI1NGNcdWM3NTggXHVhZTMwXHViMzEzXHVhYzEyXHVjNWQwICQoUF8xICsgUF8yICsgXFxjZG90cyArIFBfTikkXHVjNzQ0IFx1YWNmMVx1ZDU1YyBcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMVxcbGVxIE5cXGxlcSAxNTAwJDxcL2xpPlxyXG5cdDxsaT4kMVxcbGVxIEsgXFxsZXEgNSQ8XC9saT5cclxuXHQ8bGk+JDFcXGxlcSBQX2lcXGxlcSAxMDAwJDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kUF8xID0gUF8yID0gXFxjZG90cyA9IFBfTiA9IDEkPFwvcD5cclxuIiwic3VidGFzazIiOiI8cD4kTiBcXGxlcSAzMDAkPFwvcD5cclxuIiwic3VidGFzazMiOiI8cD5cdWNkOTRcdWFjMDAgXHVjODFjXHVjNTdkIFx1Yzg3MFx1YWM3NCBcdWM1YzZcdWM3NGM8XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIzMTQ0MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNlYXJjaCBHYW1lIiwiZGVzY3JpcHRpb24iOiI8cD5Kb25naHl1biwgYSBzdHVkZW50IGluIEtTQSwgbWFkZSBhIGdhbWUgY2FsbGVkIDxzdHJvbmc+U2VhcmNoIEdhbWU8XC9zdHJvbmc+Jm5ic3A7dG8gZW5jb3VyYWdlIHRoZSB1c2Ugb2YgdmlydHVhbCBjdXJyZW5jeSBvZiB0aGUgZmFsbCBzY2hvb2wgZmVzdGl2YWwuPFwvcD5cclxuXHJcbjxwPkluIFNlYXJjaCBHYW1lLCB5b3UgbXVzdCBmaW5kIGEgcHJlLWRldGVybWluZWQgaW50ZWdlciAkWCAoMSBcXGxlIFhcXGxlJm5ic3A7TikkIHRocm91Z2gmbmJzcDtzb21lIGd1ZXNzZXMuPFwvcD5cclxuXHJcbjxwPllvdSBpbnB1dCBhdCBtb3N0ICRLJCBwb3NpdGl2ZSBpbnRlZ2VycyBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gJE4kIGluIGVhY2ggZ3Vlc3MuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+SWYgdGhlIGlucHV0IGNvbnRhaW5zICRYJCwgdGhlIGdhbWUgZW5kcy48XC9saT5cclxuXHQ8bGk+T3RoZXJ3aXNlLCB5b3UgZ2V0IHRoZSBudW1iZXIgb2YgaW50ZWdlcnMgbGVzcyB0aGFuICRYJCBhbW9uZyB0aGUgY3VycmVudCBpbnB1dCBpbnRlZ2Vycy48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Zb3UgY29udGludWUgZ3Vlc3NpbmcgdW50aWwgdGhlIGdhbWUgZW5kcy4gSWYgeW91IG1hZGUgJG4kIGd1ZXNzZXMgaW4gdG90YWwsIHlvdXIgZmluYWwgc2NvcmUgaXMgJChLKzEpXntuLTF9JC48XC9wPlxyXG5cclxuPHA+WW91IGFyZSBhIGhhY2tlciB0cnlpbmcgdG8gZWFybiB2aXJ0dWFsIGN1cnJlbmN5IHRvIG1ha2UgSm9uZ2h5dW4gc2FkIGFuZCBidXkgYWxsIHRoZSBzbmFja3MgYW5kIHNvdXZlbmlycy4gRmluZCB0aGUgb3B0aW1hbCBzdHJhdGVneSA8c3Ryb25nPm1pbmltaXppbmc8XC9zdHJvbmc+Jm5ic3A7eW91ciBzY29yZSB0byBmaW5kIHRoZSBleHBlY3RlZCBzY29yZS48XC9wPlxyXG5cclxuPHA+PHN0cm9uZz5Ob3RlIHRoYXQgJFgkIGlzIGRldGVybWluZWQgYmVmb3JlIHVzZXIgaW5wdXQgYW5kIHRoZSBwb3NzaWJpbGl0eSBvZiAkWCQgYmVpbmcgJGkkIGlzICRcXGNmcmFje1BfaX17UF8xICsgXFxjZG90cyArIFBfTn0kLjxcL3N0cm9uZz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgJE4kIGFuZCAkSyQuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyAkTiQgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzICRQXzEsIFBfMiwgXFxjZG90cywgUF9OJC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCB0aGUgZXhwZWN0ZWQgdmFsdWUgbXVsdGlwbGllZCBieSAkKFBfMSArIFBfMiArIFxcY2RvdHMgKyBQX04pJCB3aGVuJm5ic3A7eW91IHVzZSB0aGUmbmJzcDtzdHJhdGVneSZuYnNwO21pbmltaXppbmcmbmJzcDt0aGUgZXhwZWN0ZWQgdmFsdWUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMVxcbGVxIE5cXGxlcSAxNTAwJDxcL2xpPlxyXG5cdDxsaT4kMVxcbGVxIEsgXFxsZXEgNSQ8XC9saT5cclxuXHQ8bGk+JDFcXGxlcSBQX2lcXGxlcSAxMDAwJDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kUF8xID0gUF8yID0gXFxjZG90cyA9IFBfTiA9IDEkPFwvcD5cclxuIiwic3VidGFzazIiOiI8cD4kTiBcXGxlcSAzMDAkPFwvcD5cclxuIiwic3VidGFzazMiOiI8cD5ObyBhZGRpdGlvbmFsIGNvbnN0cmFpbnRzPFwvcD5cclxuIn1d