coupons – uva 10288

There are n coupons numbered from 1 to n. How many times on average are required to make a complete set of n coupons
by selecting one coupon each time?

If the answer is an integer number, output the number. If the answer is not integer, then output the integer part of the answer followed by a space and then by the proper fraction in the format Num/Denom. The fractional part should be irreducible.

• 1 <= n <= 33

• Assume that we have already k different coupons.
• Then the probability of getting a new different coupon is (n-k)/n. The expected cost is n/(n-k).
• Thus the expected number of times to make a complete set of n coupons is n/n+n/(n-1)+…+n/1 = n(1/1+1/2+1/3+…+1/n).

• Make the fractional part irreducible after each addition to avoid any over 64 bits integers.