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
    
Programmeringsolympiadens Skolkval 2023
  •  
  • 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 04:00:00, while regular practice lets you submit solutions without any constraints.

    You must log in to register.
  • A Morötter
  • B Sifferkryptot
  • C Inomhusorientering
  • D Dragkamp
  • E The Last Carrot
You must log in to submit solutions to the problem.
{"contest_start_timestamp": null, "contest_duration": 14400, "contest_started": true, "contest_ended": true, "flexible_start_window_end_time": null, "only_virtual": true}