We will first solve the problem for general ~N,K~, then explain the subtasks.

Let ~p_{i,j}~ be the probability that the ~j^{th}~ person in line will win if there are ~i~ people left in line. If ~i = 1~, then ~j~ must be ~1~, and by definition, ~p_{1,1} = 1~ since if there is only one person left, they are declared the winner.

Note that if the ~j^{th}~ person in line survives the round, then in the next round, they are either in position ~j~ (if somebody behind them was eliminated) or position ~j-1~ (somebody ahead of them was eliminated). This suggests that ~p_{i,j}~ depends on ~p_{i-1,j}~ and ~p_{i-1,j-1}~.

In fact, we can compute the probability that somebody ahead of the ~j^{th}~ person is eliminated by summing the probabilities of being eliminated from persons ~1~ to ~j-1~. Similarly, we do this for the people behind the ~j^{th}~ person.

There exists a formula for the probability that the ~x^{th}~ person in line is eliminated, which is dependent on ~x~, ~i~, and ~K~. The formula is reasonably easy to compute, so it will not be listed here.

Thus, ~p_{i,j}~ is equal to ~p_{i-1,j-1}~ multiplied by the probability that somebody ahead of the ~j^{th}~ person is eliminated plus ~p_{i-1,j}~ multiplied by the probability that somebody behind the ~j^{th}~ person is eliminated.

For the first subtask, we manually compute the solutions by hand since there are not many of them.

For the second subtask, we perform the dynamic programming without any memoization.

For the third subtask, we perform ~\mathcal{O}(N^3)~ dynamic programming.

For the fourth subtask, we perform ~\mathcal{O}(N^2)~ dynamic programming.

For the last subtask, one can make an interesting note about the output from the previous subtasks and conjecture what the solution will be. It will not be posted here, since we don't want people copying this for free. Note however, that the formula can be proven.

Interesting fact: the pretests and samples of this problem all have an output of ~\dfrac{1}{N}~.