Problem E
Sista moroten
Det är frustrerande för Tor och hans mor att det ibland blir en morot kvar (se uppgiften Morötter). Istället för att dela den föreslår Tor att slå tärning om vem som ska få moroten. Han tar fram $N$ stycken $M$-sidiga tärningar, vars sidor är numrerade från $1$ till $M$ och har exakt lika stor sannolikhet att rullas. Han låter nu sin mor välja $K$ stycken tal, och om talen på tärningarna summerar till ett av de talen vinner hon, annars vinner Tor. Mor vill nu ha din hjälp att skriva ett program för att avgöra hennes chans att vinna om hon väljer sina utfall optimalt.
Indata
Den första raden innehåller de tre heltalen $N, M, K$ ($1 \le N, M$, $1 \le K < N \cdot M$), antalet tärningar, hur många sidor vardera tärning har och hur många utfall mor får välja.
Utdata
Skriv ut ett decimaltal – den största sannolikheten mor kan ha att vinna om hon väljer sina utfall rätt. Svaret kommer accepteras om det har ett absolut fel om högst $10^{-5}$
|
Grupp |
Poängvärde |
Gränser |
|
$1$ |
$20$ |
$n=2,m \le 100 $ |
|
$2$ |
$20$ |
$n \le 6, m \le 6 $ |
|
$3$ |
$20$ |
$n \le 50, m \le 4 $ |
|
$4$ |
$20$ |
$n \le 40, m \le 40 $ |
|
$5$ |
$20$ |
$n \le 20, m \le 5000 $ |
| 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 |
