TopCoder problem "CollectingBonuses" used in SRM 400 (Division I Level Three)

Problem Statement

A juice company is running a promotion where each juice bottle they sell contains a code that you can redeem for a prize. There are n different codes, each corresponding to a different type of prize. The codes are evenly distributed, so the probability of winning a certain type of prize is 1/n for each bottle. The codes are written underneath the bottle caps, so you can't read them until you buy the bottles. Your goal is to collect k different types of prizes. Return the expected number of bottles you must buy to achieve this goal.

Definition

Class:	CollectingBonuses
Method:	expectedBuy
Parameters:	String, String
Returns:	double
Method signature:	double expectedBuy(String n, String k)
(be sure your method is public)

Notes

The returned value must be accurate to within a relative or absolute value of 1E-9.

Constraints

n and k will contain digits ('0' - '9') only.

n and k will represent positive integers without leading zeros.

n will represent an integer between 1 and 10^18, inclusive.

k will represent an integer between 1 and the integer n represents, inclusive.

Examples

"1"

"1"

Returns: 1.0

With only 1 type of prizes you just need to buy 1 bottle.

"2"

"1"

Returns: 1.0

Now there are 2 types of prizes, but any one will satisfy you, so you again need only 1 bottle.

"2"

"2"

Returns: 3.0

First you buy 1 bottle and collect some type of prizes. After this, you need to collect another type of prizes. Only half of bottles contains it, so in average you must buy 2 more bottles to achieve your goal.

"4"

"3"

Returns: 4.333333333333333

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8764

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12172&pm=8764

Writer:

ymatsu

Testers:

PabloGilberto , Andrew_Lazarev , ivan_metelsky

Problem categories:

Math