Problem C
Mining Race
Notch is holding a race for Steve and Alex to see who is the
better miner. The rules are simple: they must each move
$n$ blocks forward and
$n$ blocks down. They can
do this in any order they choose—that is, they each mine
$2n$ times ($n$ blocks in front of them and
$n$ below them) and may
order these $2n$ mining
steps in any way they want. They will never mine above or
behind them, as that will just slow them down.
Steve and Alex do not want to take the same mining path, to avoid getting in each other’s way or mining blocks for their opponent. To avoid this, Alex decides to move $b$ blocks behind and $b$ blocks below Steve before the race begins. However, as Steve and Alex start to mine, Notch realizes there is a problem with their approach: it is still possible that they run into each other’s mining paths during the race! For example, consider the following figure:
Notch wants to know whether or not their paths will intersect. Assuming that both Steve and Alex choose their path randomly and independently (that is, each chooses a randomly-ordered sequence of $n$ moves forward and $n$ moves down), what is the probability that their paths collide during the race?
Input
The input is a single line containing two integers $n,b$ ($1 \leq b \leq n \leq 500\, 000$).
Output
Output a single line containing the probability of Steve and Alex’s mining paths intersecting. Your answer will be considered correct if its absolute or relative error doesn’t exceed $10^{-6}$.
Sample Input 1 | Sample Output 1 |
---|---|
5 3 |
0.0318877551 |
Sample Input 2 | Sample Output 2 |
---|---|
2 1 |
0.4444444444 |
Sample Input 3 | Sample Output 3 |
---|---|
3 3 |
0.0025000000 |