10. príklad

Koniec: 28. marec 2022 22:00
Do konca: kolo skončilo
Kategórie:
5
6
7
8
9
„Ďakujeme, môžeš ísť,” pustila Vella trolla, „a nie že povieš ostatným, kde nás nájdu.” Malý troll len ufujazdil medzi kamene. „Dobre, to by sme teda mali,” vydýchol si Andy, ktorého záhadná červená kniha zrazu znervózňovala. Vložil ju teda do batoha. „Už len napochodovať do jaskyne a nejako odtiaľ dostať Mimriška.” „Nebude to také jednoduché,” zachmúrene povedala Vella a ukázala na strážcu sediaceho pri vchode do jaskyne. „Vyzerá unavene,” zamyslene prehodil Majty P., „možno sa dokážeme dnu vkradnúť.”

Zadanie

Strážca jaskyne je unavený. Jeho únavu vieme vyjadriť kladným celým číslom, ktoré je na začiatku 1. Aby nezaspal, počúva nekonečný playlist pesničiek podľa svojho výberu. Každá pesnička má nejakú kvalitu, ktorú vieme tiež vyjadriť kladným celým číslom. Playlist tvoria také pesničky, že každá má vyššiu kvalitu ako tá predošlá. Keď si vypočuje pesničku kvality n, zmení sa jeho únava nasledovne:
  • Ak má únavu 1, zmení sa na 2^{(3n^2 + n)} + n \cdot 2^{(3n^2 + n + 1)}.
  • Ak má únavu x \ (x\ne1), tak sa od x odráta najmenšia mocnina dvoch taká, že nie je deliteľom x, a výsledné číslo sa potom ešte vydelí 4^n. Tým dostaneme strážcovu novú únavu.
Keď strážcovi vyjde únava, ktorá nie je kladné celé číslo, tak zaspí, čo nechce. Chce ale stráviť čo najviac času tak, že má iba únavu 1, aby vedel čulo strážiť jaskyňu. Nájdite spôsob, ako si môže strážca vybrať taký playlist, že dosiahne únavu 1 ľubovoľne veľakrát bez toho, aby zaspal.
Vzorové riešenie Odovzdať

Komentáre (0)

  • Žiadne komentáre

Pridaj komentár

Pridať komentár môžeš iba keď si prihlásený!

Prihlásiť sa