Card Game Expected Value

Time Limit: 2sMemory: 256MB

Problem

You have n cards numbered 1 through n. You draw one card uniformly at random.

Strategy: if the card's value is greater than k, you keep it. Otherwise, you discard it and draw one more card (which you must keep regardless of its value).

Compute the expected value of the card you end up with under this optimal-threshold strategy.

This type of problem (optimal stopping with a fixed threshold) appears constantly in quant interviews and underlies the secretary problem.

Input Format

Two space-separated integers n and k.

Output Format

The expected value rounded to 4 decimal places.

Examples

Example 1

Input(Two space-separated integers n and k.)

4 2

Output

3.0000

Draw 1 card from {1,2,3,4}. Keep if > 2, else draw again. E[value] = 3.0

Example 2

Input(Two space-separated integers n and k.)

6 3

Output

4.2500

6-sided die: keep if > 3, else reroll once. E[value] = 4.25

Constraints

•2 ≤ n ≤ 1000 (cards numbered 1 to n)
•1 ≤ k < n (threshold)
•Output rounded to 4 decimal places

Loading interactive editor…