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), andabout Dto 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}")