Connection Status:
Competition Arena > CollectingBonuses

CollectingBonuses

SRM 400 · 2008-05-01 · by ivan_metelsky

SRM 400 · 2008-05-01 · by ivan_metelsky · Math
Class Name: CollectingBonuses
Return Type: double
Method Name: expectedBuy
Arg Types: (string, string)
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.

Statement by TopCoder, Inc. — view the original on the archive.

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

Submitting as anonymous