CollectingBonuses
SRM 400 · 2008-05-01 · by ivan_metelsky
SRM 400 · 2008-05-01 · by ivan_metelsky · Math
Problem Statement
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.
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)
"999999999999999999" "999999999" Returns: 9.999999995E8
4)
"999999999999999999" "999999999999999999" Returns: 4.202374733879435E19
Submissions are judged against all 200 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CollectingBonuses with a public method double expectedBuy(string n, string k) · 200 test cases · 2 s / 256 MB per case