ICPC Asia Jakarta 2020 Official Team Training 2 (16 Dec)


2020-12-15 18:00 AKST

ICPC Asia Jakarta 2020 Official Team Training 2 (16 Dec)


2020-12-15 23:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -523 days 22:02:47

Time elapsed


Time remaining


Problem I

Created with Imgflip GIF Generator

Jacob is playing a very odd solo card game called StopCard. In this game, the deck consists of $n$ cards where every card has one unique integer written on one side of it. The deck is shuffled randomly before the game is played. During each turn of the game, Jacob can choose to either take a card off the top of the deck and read that value, or not take a card off the deck and end the game. His final score for the game is the value of the last card taken from the deck. The deck will always have at least one card, and the first turn of the game must always be to draw the top card of the deck.

Jacob has a basic understanding of optimal stopping theory, so he devises a plan to play the game somewhat effectively. His plan is to keep drawing cards for a predetermined number ($c$) of times, then to keep going until he sees a card that is larger than all the cards he previously saw, then to stop. His score will be the value written on that card. If he never sees a larger value on a card than the first cards he skipped, he would continue drawing until the deck runs out and would be left with a score equal to the number on the last card in the deck.

What is Jacob’s expected score under this strategy?


The input consists of a single test case. The first line contains two integers $n$ and $c$ denoting the number of cards in the deck ($0 < n \le 64$) and $c$ is the number of cards Jacob will definitely draw ($0 \le c < n$). The second line contains $n$ distinct integers $a_ i$ ($0 \le a_ i \le 10\, 000$) - the numbers written on the cards in the deck, which may be given in any order.


Output the expected score under Jacob’s strategy. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-5}$.

Sample Input 1 Sample Output 1
2 1
0 1
Sample Input 2 Sample Output 2
4 2
0 4 8 6
Sample Input 3 Sample Output 3
15 7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Sample Input 4 Sample Output 4
5 0
10000 9832 3242 2 42