A typical Gachapon machine, filled with toys inside.
Gachapon are small coin-operated mechanisms, where somebody inserts a coin, turns a knob, and then receives an item, similar to a gumball machine. However instead of gum or candy, Gachapon machines usually contain small toys (confusingly, often both the machines and the toys are referred to as "Gachapon"). These toys are often part of a "set" of similar objects or characters, and people are encouraged to collect all toys in a set. However due to the random nature of the machine, one might find themselves inserting many coins before receiving at least one of each toy in the set (while having received possibly many multiples of some items).
Problem Statement
Kaito is a young boy who is an avid fan of his favorite television cartoon
show. One day while out shopping, he spots a Gachapon machine filled with small
plastic toys of his favorite characters from the show! Even better, each toy
only costs a single cent to dispense! He asks his mother for some spare change,
then gets to work inserting pennies and turning the crank to dispense the toys,
with the goal of collecting at least one copy of each character.
If there are N different toys in the set (each with equal probability of being
dispensed), how many pennies would Kaito expect to spend before collecting at
least one of each toy in the set?
Input Data
First line will be Q, the quantity of testcases.
Q lines will then follow, each with a single value N the number of unique
items in the set.
Answer
Should consist of Q space-separated values, corresponding to the expected
value of pennies to be spent before receiving at least one of each type of item.
Assume that each type of item has an equal chance of being dispensed each time.
That is, the result of one dispense does not impact the result of any other
dispense.
Error should be less than 1e-6
Example
input data:
3
1
23
456
answer:
1.0 85.888705 3055.566882