Herkules a hydry
V dávnych časoch Herkules bojoval so štvorhlavou hydrou. To by nebolo zaujímavé, keby hydra nebola skoro nesmrteľná.
Keď jej Herkules odťal jednu hlavu neostala jedna trojhlavá ale dve trojhlavé hydry. Keď potom odťal hlavu jednej z tých trojhlavých, nevznikla jedna dvojhlavá hydra ale tri dvojhlavé. Keď odťal hlavu jednej z dvojhlavých, vznikli z nej štyri jednohlavé.
Pri takomto postupe by po treťom odseknutí hlavy, boli z pôvodnej štvorhlavej hydry jedna trojhlavá, dve dvojhlavé a štyri jednohlavé.
Všeobecne:
Keď Herkules odtne hlavu n-hlavej hydre, vznikne nie (n-1)hlavá hydra ale hneď (K+1) (n-1)hlavých hydier. Kde K je počet hláv, ktoré Herkules hydre/hydrám už odťal.
Keď odtne hlavu jednohlavej hydre, táto hydra zanikne v ohni pekelnom. Samozrejme K sa zvýši - hlavu odťal.
Vašou úlohou je nájsť najlepší a najhorší postup, t. j. koľkokrát musí Herkules odťať hlavu, ak si to dobre premyslel a nechce sa trápiť, a koľkokrát ak si to dobre premyslel a chce si čo najviac potrénovať.
Ako dlho mu to bude trvať v jednotlivých variantoch, ak každú sekundu odtne jednu hlavu?
Nájsť postupy nie veľký problém ale spočítať trvanie už áno. Preto malá pomoc: Minizápas bude trvať niečo nad minútu. Maxi zápas niečo "málo" nad 700 000 rokov.
Riešenie na ockin.science
