Chocolate
Time limit1sMemory limit128 MB
For C equally likely colors, after N draws where matching pairs are eaten, find the probability that exactly M colors remain on the table.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Combinatorics, Probability, Math
- Solved
- No attempts yet
Problem
You have a large package of chocolates that come in different colors, and every color is equally likely to be drawn. You repeatedly take one chocolate at a time and place it on the table.
Whenever two chocolates of the same color are on the table, you immediately eat both of them and remove them from the table. Because of this rule, every color that is on the table appears at most once, so the number of chocolates on the table equals the number of distinct colors currently present.
Given the number of colors , a number of draws , and a target count , compute the probability that exactly chocolates remain on the table after chocolates have been drawn.
Input
The input contains several test cases, one per line. Each test case is a line with three non-negative integers , , and ( and ).
The input is terminated by a line containing a single zero, which is not a test case and must not be processed.
Output
For each test case, print on its own line the probability that exactly chocolates are on the table after draws, rounded to exactly three decimal places.