Problem E
The Last Carrot
Languages
en
sv
It’s frustrating for Tor and his mother that sometimes there’s a carrot left (see the task Carrots). Instead of sharing it, Tor suggests rolling dice to decide who gets the carrot. He takes out $N$ dice, each with $M$ sides, numbered from $1$ to $M$, each with an equal probability of being rolled. He then lets his mother choose $K$ numbers, and if the numbers on the dice sum up to one of those numbers, she wins; otherwise, Tor wins. Now, Mother wants your help to write a program to determine her chances of winning if she chooses her outcomes optimally.
Input
Input consists of the the three integers $N, M, K$ ($1 \le N \le 20$, $1 \le M \le 5000$, $1 \le K < N \cdot M$), the number of dice, how many sides each dice has and how many outcomes Mother can choose.
Output
Print a real number: the probability that Mother will win if she chooses her outcomes optimally. The answer will be considered correct if it has an absolute error of at most $10^{-5}$.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
|
Group |
Points |
Constraints |
|
$1$ |
$20$ |
$N=2, M \le 100 $ |
|
$2$ |
$20$ |
$N \le 6, M \le 6 $ |
|
$3$ |
$20$ |
$N \le 12, M \le 12 $ |
|
$4$ |
$20$ |
$N \le 20, M \le 100 $ |
|
$5$ |
$20$ |
No additional constraints. |
| Sample Input 1 | Sample Output 1 |
|---|---|
2 6 2 |
0.305555555555556 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 7 4 |
0.41399416909621 |
| Sample Input 3 | Sample Output 3 |
|---|---|
20 2189 2734 |
0.369028440650235 |
