Game Show Elimination

Time limit8sMemory limit2048 MB

Summary

Given n contestants with uniform skill ranges [i, i+k], find each contestant's expected rank when the weekly runner-up is eliminated until one remains.

Level: Medium7 of 10
Topics: Probability, Dynamic programming
Solved: No attempts yet

Problem

You are running an elimination-style game show. Players are eliminated one at a time until only one remains. Using what you know about the contestants, you predict the results.

Each week, the remaining contestants take part in a competition. Each contestant's score is a random real number within that contestant's own skill range. The contestants are ranked from highest to lowest score. Since scores are real numbers, the probability of a tie is zero.

The winner of the week's competition chooses who is eliminated. All players believe they should pick whoever did best after them, so the winner always eliminates the second place contestant. That contestant leaves the show. This repeats week after week until one contestant is left.

A contestant's final rank depends on when they leave. The last contestant to leave (the winner) gets rank $1$ , the second-to-last gets rank $2$ , and so on, until the first person to leave gets the lowest rank.

Given the skill ranges, compute the expected rank of each player.

Input

The single line of input contains two integers $n$ ( $2 \leq n \leq 1\,000$ ) and $k$ ( $2 \leq k \leq 10$ ), where $n$ is the number of contestants and $k$ determines the skill range. Contestants are numbered from $1$ to $n$ . The skill range of contestant $i$ is from $i$ to $i+k$ inclusive, and their score each week is a random real number in this range.

Output

Output $n$ lines. Each line contains a single real number, the expected rank of a contestant, listed in contestant number order. Answers are accepted within an absolute or relative error of at most $10^{-6}$ .

Examples1

Example 1
Input
```
3 2
```
Expected output
```
2.109375
2.625000
1.265625
```