RareItems
SRM 729 · 2018-02-08 · by erinn
Problem Statement
You are interested in purchasing a colleciton of items. Sadly, they are only sold as "blind bags" where you do not know which item you will receive until you open it. The frequency of receiving each type of item is given in
Given that each item you receive is selected at random according to the given frequency, and that you will continue purchasing items until you have one of each, what is the averge number of purchases you will expect to make to have a complete collection?
Constraints
- frequency will contain between 1 and 20 elements, inclusive.
- Each element of frequency will be between 1 and 1000, inclusive.
{1}
Returns: 1.0
There is only one item, so on your first purchase, you complete your collection.
{2,2}
Returns: 3.0
On your first purchase, you get an item you don't yet have. On your second purchase, one of two things happens (with equal probability): you either get the item you need (and thus complete your colleciotn), or else get the same item you already have, and then have to keep buying.
{1,1,100}
Returns: 153.00019801980199
Like many collectibles, getting the rare item can take a while.
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
Returns: 263.58466676215386
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: 71.9547931428736
Submissions are judged against all 19 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RareItems with a public method double expectedPurchases(vector<int> frequency) · 19 test cases · 2 s / 256 MB per case