Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Mariánovi Horňákovi na
V predchádzajúcej sérii ste sa stretli s genetickými inžiniermi z Absurdistanu, ktorým ste pomohli navrhnúť rastliny produkujúce presné množstvá plodov každý rok. Projekt mal skvelý marketing a získal tisíce podporovateľov, ktorí si na niekoľko rokov dopredu objednali svoje ovocie. Slávou omámení inžinieri sa teda rozhodli pustiť do ešte ambicioznejšieho problému. Do presného a rýchleho plánovania úrody termosenzitívneho ovocia.
Úroda termosenzitívneho ovocia závisí od toho, či bol konkrétny rok studený alebo teplý. Pre obe situácie je presne určený počet aj typ plodov, ktoré na rastline vyrastú. Vedci dokážu ovládať počasie natoľko, aby vynútili konkrétne správnie rastlín v každom roku. Teraz potrebujú zistiť, ako sa majú teplé a studené roky striedať tak, aby čo najskôr dosiahli úrodu konkrétnej veľkosti. Pomôžete im?
Úloha
Táto úloha nadväzuje na úlohu z prechádzajúceho kola. Pred tým, než budete pokračovať v čítaní, pozrite si zadanie a prípadne aj vzorové riešenie minulej úlohy.
Rastliny budeme v tejto úlohe označovať veľkými písmenami anglickej abecedy. Každá rastlina bude mať určené, aké plody na nej dozrievajú počas teplého roka a aké počas studeného roka. Toto zapíšeme tak, že za písmeno, ktoré zodpovedá rastline, napíšeme šípku a za tú písmená tých rastlín, ktorých plody na nej dozrejú. Nad šípkou uvedieme \(T\) alebo \(S\), podľa toho, či je to pravidlo pre teplý alebo pre studený rok. Ak na rastline nič nevyrastie, zapíšeme to ako \(\rightarrow 0\). Kompletná sada pravidiel potom môže vyzerať nasledovne:
| \[\text{A}\xrightarrow{T}\text{B}\] | \[\text{A}\xrightarrow{S}0\] |
| \[\text{B}\xrightarrow{T}\text{AB}\] | \[\text{B}\xrightarrow{S}\text{B}\] |
Každý typ rastliny musí mať priradené práve jedno pravidlo pre teplý rok a práve jedno pravidlo pre studený rok. Na poradí písmen nezáleží, teda \(\text{B}\xrightarrow{T}\text{AB}\) je totožné s \(\text{B}\xrightarrow{T}\text{BA}\).
V každom roku zasadíme všetky semená, ktoré máme. Podľa teploty, ktorú si zvolíme, potom vyrastie rastlina aj s plodmi. Každý plod obsahuje práve jedno semeno, ktoré zasadíme v ďalšom roku. Ak by sme sa teda riadili podľa vyššie uvedeného príkladu, mohla by sa úroda vyvíjať ktoroukoľvek z nasledovných možností: \[\text{A}\xrightarrow{T}\text{B}\xrightarrow{S}\text{B}\xrightarrow{T}\text{AB}\xrightarrow{T}\text{BAB}\xrightarrow{T}\text{ABBAB}\xrightarrow{S}\text{BBB}\xrightarrow{T}\text{ABABAB}\] \[\text{A}\xrightarrow{T}\text{B}\xrightarrow{T}\text{AB}\xrightarrow{T}\text{BAB}\xrightarrow{T}\text{ABBAB}\xrightarrow{T}\text{BABABBAB}\xrightarrow{S}\text{BBBBB}\] \[\text{A}\xrightarrow{S}0\xrightarrow{T}0\xrightarrow{S}0\]
Postupne si teraz predstavíme tri sady pravidiel, ukážeme si príklad vývoja úrody a položíme niekoľko otázok o tom, akú veľkú úrodu možno zostrojiť.
Ananásová sada
Ananásová sada je pomerne jednoduchá. Začíname s ananásom (\(A\)), na ktorom okrem malého ananásu vyrastú aj nejaké bobule. Tie sa však už ďalej nemnožia, keďže z bobule vyrastie práve jedna bobuľa bez ohľadu na teplotu. Pravidlá sú nasledovné:
| \[\text{A}\xrightarrow{T}\text{ABBB}\] | \[\text{A}\xrightarrow{S}\text{AB}\] |
| \[\text{B}\xrightarrow{T}\text{B}\] | \[\text{B}\xrightarrow{S}\text{B}\] |
Ak by sme chceli dosiahnuť \(9\) plodov, mohli by sme to spraviť napríklad takto:
\[\text{A}\xrightarrow{T}\text{ABBB}\xrightarrow{S}\text{ABBBB}\xrightarrow{T}\text{ABBBBBBB}\xrightarrow{S}\text{ABBBBBBBB}\]
- (1 bod) Nájdite takú postupnosť teplých a studených rokov, že úroda po posledom roku bude obsahovať presne \(42\) plodov.
- (2 body) Po koľkých rokoch najskôr a po koľkých rokoch najneskôr možno dosiahnuť úrodu obsahujúcu presne \(4247\) plodov?
Citrónová sada
Citrónová sada obsahuje ešte dyňu a egreš. V teplom roku vyprodukuje každá rastlina dva plody. V studenom roku je aktívny len citrón, dyňa s egrešom len zachovajú rod. Na začiatku máme jeden citrón (\(C\)).
| \[\text{C}\xrightarrow{T}\text{CE}\] | \[\text{C}\xrightarrow{S}\text{DE}\] |
| \[\text{D}\xrightarrow{T}\text{CE}\] | \[\text{D}\xrightarrow{S}\text{D}\] |
| \[\text{E}\xrightarrow{T}\text{EE}\] | \[\text{E}\xrightarrow{S}\text{E}\] |
Ak by sme chceli dosiahnuť \(9\) plodov, mohli by sme to spraviť napríklad takto:
\[\text{C}\xrightarrow{S}\text{DE}\xrightarrow{T}\text{CEEE}\xrightarrow{T}\text{CEEEEEEE}\xrightarrow{S}\text{DEEEEEEEE}\]
- (1 bod) Nájdite takú postupnosť teplých a studených rokov, že úroda po posledom roku bude obsahovať presne \(42\) plodov.
- (2 body) Nájdite takú postupnosť teplých a studených rokov, že úroda po posledom roku bude obsahovať presne \(4247\) plodov.
- (4 body) Vieme zostrojiť vhodnú postupnosť rokov pre úrodu každej veľkosti? Pokiaľ áno, vysvetlite, ako by ste takúto postupnosť zostrojili. Pokiaľ nie, uveďte protipríklad a vysvetlite, prečo sa nedá dopestovať dané množstvo plodov.
Fibonacciho sada
Fibbonaciho sada počas teplých rokov produkuje Fibbonaciho postupnosť spomenutú v minulom kole. Na studený rok je však extrémne citlivá. Začiname s rastlinou \(F\) a pravidlá budú totožné s tými použitými ako príklad na začiatku tejto úlohy.
| \[\text{F}\xrightarrow{T}\text{G}\] | \[\text{F}\xrightarrow{S}0\] |
| \[\text{G}\xrightarrow{T}\text{FG}\] | \[\text{G}\xrightarrow{S}\text{G}\] |
Ak by sme chceli dosiahnuť \(9\) plodov, mohli by sme to spraviť napríklad takto:
\[\text{F}\xrightarrow{T}\text{G}\xrightarrow{T}\text{FG}\xrightarrow{T}\text{GFG}\xrightarrow{T}\text{FGGFG}\xrightarrow{S}\text{GGG}\xrightarrow{T}\text{FGFGFG}\xrightarrow{T}\text{GFGGFGGFG}\]
- (2 body) Nájdite takú postupnosť teplých a studených rokov, že úroda po posledom roku bude obsahovať presne \(42\) plodov.
- (3 body) Vieme zostrojiť vhodnú postupnosť rokov pre úrodu každej veľkosti? Pokiaľ áno, vysvetlite, ako by ste takúto postupnosť zostrojili. Pokiaľ nie, uveďte protipríklad a vysvetlite, prečo sa nedá dosiahnuť.
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.