Problem G
Lucky Shirt
In order to keep a fresh supply of clean shirts, you sometimes also do laundry at night, washing all shirts in the laundry basket (including the one you wore that day). This is not according to some neat schedule however; the number of days between your wash cycles is a uniformly random integer between $1$ (in which case you would wash only a single shirt) and the number of shirts you have. After washing your clothes, you put them back on top of the stack in a uniformly random order.
It is now the night after a successful programming contest, and you decide that the T-shirt you got there is your lucky shirt from now on. You wonder when you will be able to wear it again, and entertain yourself with thoughts about the good fortune you will receive when you do. You just completed your laundry and put all your shirts on the stack. Knowing the current position of your lucky shirt in the stack, what is the expected position of your lucky shirt after $k$ more washing cycles?
Input
The input consists of:
-
One line containing three integers $n$ ($1\leq n\leq 10^6$), the number of shirts you have, $i$ ($1\leq i\leq n$), the position of your lucky shirt counted from the top, and $k$ ($1\leq k\leq 10^6$), the number of washing cycles.
Output
Output the expected position of your lucky shirt after $k$ washing cycles. Your answer should have an absolute or relative error of at most $10^{-6}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 2 2 |
1.833333333 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 1 1 |
2.0 |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 7 100 |
5.499986719 |
