Sista moroten

Time: 1.0 s Memory: 1024 MB

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 \le 20$, $1 \le M \le 5000$, $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 12, m \le 12 $
$4$	$20$	$n \le 20, m \le 100 $
$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

Authors: Joshua Andersson License: CC BY-SA

Chalmers Coding Camp 24 problems

To solve the problems, you can either start a virtual contest or register for regular practice. A virtual contest simulates a participation in the original contest with a duration of 4 days, while regular practice lets you submit solutions without any constraints.

You must log in to register.
A The Last Carrot

You must log in to submit solutions to the problem.