JOIN
Get Time

   Problem Statement  

 Problem Statement for CollectingBonuses

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

0)
    
"1"
"1"
Returns: 1.0
With only 1 type of prizes you just need to buy 1 bottle.
1)
    
"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"
"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.
3)
    
"4"
"3"
Returns: 4.333333333333333

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 400 Round 1 - Division I, Level Three