Woburn Challenge 2018-19 Round 2 - Senior Division
Ilsa Faust, an experienced former MI6 agent, has agreed to join the IMF and work alongside Ethan Hunt!
As part of her onboarding process at the secret IMF headquarters in Ottawa, Ilsa is required to complete a training exercise involving defusing a bomb. However, she feels that simply defusing a bomb would be an insultingly easy task for her, so she's going to show off her multitasking skills and defuse bombs all at once!
Each bomb becomes defused as soon as two particular wires are both cut. As such, Ilsa will need to cut wires in total to complete the exercise.
It's understandably rather difficult to keep track of that many wires, so Ilsa is going to cut the wires in a random order. Specifically, until she's all done, she'll repeatedly select one of the remaining uncut wires at uniform random, and cut it.
Ethan was hoping to meet up with Ilsa, but he's walked in while the training session is underway, at a random point in time after she's cut some unknown number of wires between and , inclusive (and so has defused between and bombs, inclusive). Note that all possible values of are equally likely before Ethan enters the room. Upon entering, he'd like to estimate how much longer Ilsa will be busy. It's too difficult to count exactly how many wires Ilsa has already cut, but Ethan counts that bombs have been defused so far. Given that fact, what's the expected number of remaining wires Ilsa has yet to cut?
Subtasks
In test cases worth of the points, .
In test cases worth another of the points, .
Input Specification
The first and only line of input consists of two space-separated integers, and .
Output Specification
Output a single real number, the expected number of remaining wires Ilsa has yet to cut. Your answer must have at most absolute or relative error to be judged as correct.
Sample Input 1
1 0
Sample Output 1
1.5
Sample Input 2
2 0
Sample Output 2
3.125
Sample Input 3
2 1
Sample Output 3
1.25
Sample Explanation
In the first case, when the single bomb hasn't yet been defused, it's equally likely that Ilsa has cut either or wires so far (and so has either or wires remaining). Therefore, the expected number of wires she has yet to cut is .
Comments