Collecting coupons

Each cereal box holds one of n toys, all equally likely. How many boxes do you expect to open to collect k different toys?

What to build

A program that computes an expected waiting time with linearity of expectation.

Requirements

  • Print expected boxes F, the exact expected number of boxes as a reduced fraction (a whole number when it is one), and about D to 2 decimal places.

Input

One line: n and k.

Output

Two lines.

Constraints

1 ≤ k ≤ n ≤ 100.

Example

Input:

6 6

Output:

expected boxes 147/10
about 14.70

Why it works

The total wait is a sum of separate waits, one for each new toy; each wait has expected length n ÷ (n − i), and expected values add even though the waits are random.

Examples

Example 1 · Input
6 6
Expected output
expected boxes 147/10
about 14.70
Example 2 · Input
2 2
Expected output
expected boxes 3
about 3.00

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

When you already have i different coupons, a new box gives a new one with probability (n − i) ÷ n.

Hint 2

The expected wait for that is n ÷ (n − i) boxes; by linearity, add the waits for i = 0 to k − 1.

Solution

Show one correct solution (try it yourself first)
from fractions import Fraction

n, k = map(int, input().split())
expected = sum(Fraction(n, n - i) for i in range(k))
print("expected boxes", expected)
print(f"about {float(expected):.2f}")

Lesson: Random variables and expected value →