Zadanie
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ť.
Po tom, čo si od vás genetickí inžinieri z Absurdistanu dva krát vypýtali pomoc, zistili, že skupinka informatikov riešila podobné problémy už pred vami. Kľúčové slovo, ktoré treba gúgliť je L-Systém. Na wikipédii nájdete okrem iného aj kopu pekných obrázkov, takže by ste sa tam určite mali aspoň pozrieť. Ak by ste sa však pokúsili nájsť niečo o Ananásovej, Citrónovej alebo Fibonacciho sade pravidiel, veľa by ste toho nenašli. Preto si o nich niečo povieme tu.
Ananásová sada
| \[\text{A}\xrightarrow{T}\text{ABBB}\] | \[\text{A}\xrightarrow{S}\text{AB}\] |
| \[\text{B}\xrightarrow{T}\text{B}\] | \[\text{B}\xrightarrow{S}\text{B}\] |
Už v zadaní sa objavila nápoveda, že každé bobulové semeno vyprodukuje jedno nové do ďalšieho roku a teda sa zachová bez ohľadu na teplotu. Ananás taktiež zachová sám seba a ešte popri tom vyprodukuje nejaké nové bobule. V teplom roku tri, v studenom iba jednu. Začínajúc s jedným ananásom teda vieme každý rok vyprodukovať o jeden alebo o tri plody viac ako v tom predošlom. Asi vás teda neprekvapí, že po dostatočne dlhej dobe vieme dosiahnuť ľubovoľný počet plodov.
Požadovaných \(42\) plodov dosiahneme napríklad po \(41\) studených rokoch. Prečo sa ponáhľať? V duchu tohto hesla môžeme pokračovať aj pri najneskoršom dosiahnutí \(4247\) plodov. Bude na to treba len \(4246\) studených rokov. Winter is coming! Ak by sme, naopak, chceli \(4247\) plodov čo najskôr, potrebovali by sme \(4246 \div 3 = 1415 + \frac{1}{3}\) teplých rokov. Keďže výsledok nie je celé číslo, budeme ich musieť doplniť jedným studeným rokom.
Správne odpovede teda sú:
- \(42\) plodov dosiahneme napríklad postupnosťou \(41\) studených rokov
- \(4247\) plodov dosiahneme najskôr po \(1416\) rokoch a najneskôr po \(4246\) rokoch.
Citrónová sada
| \[\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}\] |
Človek by si povedal, že egreše sú len obyčajné bobule. A počas studených rokov je to aj pravda – len zachovávajú svoj rod. Avšak počas teplých rokov sa zákerne zdvojnásobia. Také niečo by sa citrónu s dyňou nemohlo stať. Z týchto dvoch plodín každý rok totiž existuje iba jedna a to práve jeden kus. V teplom roku vyrastie na ich rastlinách nový citrón (presne jeden) a v studenom zase nová dyňa (znova presne jedna). Môžeme teda povedať, že v závislosti od teploty predošlého roka, máme zasadený jeden citrón alebo jednu dyňu a niekoľko egrešov.
Pozrime sa teraz na situáciu z iného uhľa. V teplom roku každá rastlina vyprodukuje dve semená a teda celkový počet semien bude na konci roka dvojnásobný. V studenom roku vieme vypestovať iba o jeden egreš viac a aj to len v prípade, že máme citrón (a teda predošlí rok bol teplý). V každom ďalšom studenom roku už nenastane žiadna zmena v zložení semien.
Počet semien teda môžeme buď zdvojnásobiť alebo zväčšiť o jedna. Po každom zväčšení však musíme znova zdvojnásobovať – možno nie hneď rok na to, ale ak príde opäť studený rok, nič sa nezmení. Možný vývoj situácie vieme odsledovať na nasledujúcom diagrame. Šípky nadol predstavujú teplé roky, šípky doprava predstavujú studené roky. Aby sa nám všetky egreše zmestili na obrazovku (a vy ste ich nemuseli počítať) budeme jeden citrón a \(n\) egrešov písať ako \(\text{C}\text{E}^n\).
Môžeme si všimnúť, že po najviac troch teplých a troch studených rokoch, vieme dosiahnuť ľubovoľný počet plodov od jedného až po \(15\). To nám napovedá, že by sme mohli vedieť dosiahnuť ľubovoľný počet plodov. Skúsme sa na situáciu pozrieť od konca:
- Ak sa v nejakom roku urodil nepárny počet plodov, musel tento rok byť studený. V teplých rokoch sa totiž počet plodov zdvojnásobí a teda je nutne párny.
- Ak sa v nejakom roku urodil párny počet plodov, mohol to byť teplý rok. Vo väčšine prípadov dokonca aj musel, skúste sa zamyslieť, prečo.
Tieto dve pozorovania nám stačia na to, aby sme vymysleli univerzálny postup na dosiahnutie ľubovoľne veľkej úrody. Ak chceme dosiahnuť nepárnu úrodu, prehlásime posledný rok za studený a od úrody odpočítame jeden plod. Ak chceme dosiahnuť párnu úrodu, prehlásime posledný rok za teplý a úrodu predelíme dvoma. Na zvyšnú úrodu aplikujeme ten istý postup a opakujeme ho až kým nám nezostane úroda veľkosti jedna, čo je počiatočný citrón. V každej situácii teda vieme, čo máme robiť. Navyše, nestane sa nám, že by sme potrebovali dva studené roky po sebe, pretože studený rok použijeme iba na vytvorenie nepárne veľkej úrody a teda rok predtým bola párne veľká, čiže rok bol teplý.
Pozrime sa na vývoj pri niekoľkých úrodách:
\[42\xleftarrow{T}21\xleftarrow{S}20\xleftarrow{T}10\xleftarrow{T}5\xleftarrow{S}4\xleftarrow{T}2\xleftarrow{T}1\]
\[4247\xleftarrow{S}4246\xleftarrow{T}2123\xleftarrow{S}2122\xleftarrow{T}1061\xleftarrow{S}1060\xleftarrow{T}530\xleftarrow{T}265\] \[265\xleftarrow{S}264\xleftarrow{T}132\xleftarrow{T}66\xleftarrow{T}33\xleftarrow{S}32\xleftarrow{T}16\xleftarrow{T}8\xleftarrow{T}4\xleftarrow{T}2\xleftarrow{T}1\]
\[23\xleftarrow{S}22\xleftarrow{T}11\xleftarrow{S}10\xleftarrow{T}5\xleftarrow{S}4\xleftarrow{T}2\xleftarrow{T}1\]
Vyriešili sme teda všetky problémy:
- Hľadaná postupnosť je \(\text{TTSTTST}\)
- Hľadaná postupnosť je \(\text{TTTTTSTTTSTTSTSTS}\)
- Vieme zostrojiť ľubovoľne veľkú úrodu. Postup sme popísali vyššie.
Fibonacciho sada
| \[\text{F}\xrightarrow{T}\text{G}\] | \[\text{F}\xrightarrow{S}0\] |
| \[\text{G}\xrightarrow{T}\text{FG}\] | \[\text{G}\xrightarrow{S}\text{G}\] |
Pozrime sa najskôr čo sa deje pri dlhých postupnostiach teplých rokov.
| Po roku | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Počet F | 1 | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 |
| Počet G | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 |
| Počet Spolu | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 |
Môžeme si všimnúť, že počty písmen \(\text{F}\), počty písmen \(\text{G}\) ako aj počty písmen spolu tvoria fibonacciho postupnosť. (Vedeli by ste odôvodniť prečo?) Pokiaľ však príde jeden alebo viac studených rokov, všetky \(\text{F}\) nám vyhynú a počet \(\text{G}\) sa nezmení. V nasledujúcom teplom období si potom každé \(\text{G}\) začne nezávisle rozvíjať svoju fibonacciho postupnosť. Každá z týchto postupností sa rozvinie do rovankého bodu pred ďalším studeným blokom, kde sa z nich znova stanú nezávislé začiatky postupností. Takto sa vieme vystriedať ľubovoľne veľa krát a výsledok teda bude súčin niekoľkých členov fibonacciho postupnosti.
Napríklad \(42\) je súčin \(2\) a \(21\). Vieme teda počas troch teplých rokov zgenerovať \(\text{GFG}\), ktoré jedným studeným rokom zredukujeme na \(\text{GG}\) a následne počkáme ešte \(6\) teplých rokov, kým každé z oboch \(\text{G}\) vyprodukuje \(21\) plodov.
Úrody veľkosti \(1\), \(2\), \(3\), \(4 = 2 \cdot 2\), \(5\) a \(6 = 2 \cdot 3\) teda zostrojiť vieme. Číslo \(7\) však nie je členom fibonacciho postupnosti a keďže je to prvočíslo, nevieme ho zapísať ako súčin iných prirodzených čísel. Úrodu veľkosti \(7\) teda nevieme dosiahnuť.
Tým sme zodpovedali aj posledné dve otázky:
- Hľadaná postupnosť je \(\text{TTTSTTTTTT}\)
- Nevieme dosiahnuť napríklad \(7\) plodov.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.