Woburn Challenge 2018-19 Round 2 - Senior Division

Problem 3: Multitasking

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 N (1 ≤ N ≤ 2,000) bombs all at once!

Each bomb becomes defused as soon as two particular wires are both cut. As such, Ilsa will need to cut 2N 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 2N 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 x between 0 and 2N − 1, inclusive (and so has defused between 0 and N − 1 bombs, inclusive). Note that all 2N possible values of x 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 K (0 ≤ K ≤ N − 1) 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 9/25 of the points, N ≤ 5.
In test cases worth another 12/25 of the points, N ≤ 200.

Input Format

The first and only line of input consists of two space-separated integers, N and K.

Output Format

Output a single real number, the expected number of remaining wires Ilsa has yet to cut. Your answer must have at most 10⁻⁵ 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 0 or 1 wires so far (and so has either 2 or 1 wires remaining). Therefore, the expected number of wires she has yet to cut is (2 + 1)/2 = 1.5.

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 128M
Added: Dec 14, 2018
Author: wjomlex

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)