Zadanie
Táto úloha je teoretická. Ako svoje riešenie odovzdaj pdf súbor, v ktorom bude tvoje riešenie aj so zdôvodnením, prečo je správne. Po konci kola ti riešenie opraví vedúci, a napíše ti komentár - povie ti kde si spravil chyby, prípadne ti poradí ako vieš svoje riešenia zlepšiť.
Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Štepimu na [email protected]
Žirafa Amanda sa prechádza po savane, keď tu zrazu natrafí na strom s ovocím. Príde k nemu, odtrhne si nejakú vetvu s ovocím a zje ju. Potom si ale uvedomí, že by ovocia nemala zjesť príliš veľa, aby sa neprejedla. Chcela by si teda aspoň pamätať, koľko toho ovocia už zjedla. Bohužiaľ, už zabudla, aké veľké bolo to ovocie, ktoré práve zjedla. Tak si namiesto toho napíše, aké veľké je to ovocie, ktoré na strome ostalo najbližšie k tomu odtrhnutému. No a keď už to tak začala robiť, tak v tom pokračuje, až kým takto nezje celý strom.
Stromy a postupnosti
Strom si môžeme predstaviť tak, že má kmeň, na ktorom rastie kus ovocia, a z neho sa potom oddeľuje niekoľko ďalších vetiev, na ktorých môže rásť ďalšie ovocie a tie sa môžu ďalej rozvetvovať. Okrem toho si môžeme ovocia na strome očíslovať podľa veľkosti \(1\) až \(n\), toto číslo budeme nazývať veľkosť ovocia.
Strom teda môže vyzerať napríklad takto:
Ovocia, z ktorých už nerastú žiadne ďalšie vetvy, nazveme listy (lebo na takých miestach na strome zvyčajne rastú listy).
Amanda papá ovocie zo stromu takýmto spôsobom: Spomedzi všetkých listov si vyberie ten s najmenším ovocím, odtrhne ho aj s vetvou, ktorou je prichytené k najbližšiemu ovociu, a zje ho. Zapíše si veľkosť toho najbližšieho ovocia, ktoré zostalo na strome, a potom takto pokračuje ďalej, až kým neostane len posledné ovocie na kmeni.
Pre strom na obrázku má Amanda na začiatku na výber listy \(1, 2, 5, 7\). Z nich odtrhne ten najmenší, teda \(1\). Ten susedí s listom \(4\), teda si zapíše \(4\). Ďalej by pokračovala odtrhnutím listu \(2\), teda by si zapísala \(6\). Takto pokračuje, až kým nezostane len jediný list \(3\). Zapísala by si teda postupnosť \(4, 6, 3, 3, 4, 3\).
Úlohy
(10 bodov) Akú postupnosť by si zapísala Amanda pri jedení tohto stromu?
(20 bodov) Z nejakého stromu si Amanda zapísala postupnosť \(3, 3, 3, 3, 3, 3\). Ako mohol taký strom vyzerať?
(20 bodov) A ako mohol vyzerať strom, z ktorého vznikla postupnosť \(5, 2, 7, 3, 6, 1, 8, 4\)?
(20 bodov) Amanda by zo svojich zápiskov rada zistila, koľko “detí” má nejaké ovocie. Ovocie \(A\) nazveme dieťaťom ovocia \(B\), ak spolu susedia (teda sú priamo spojené vetvou) a \(A\) je v strome hlbšie ako \(B\). Teda napríklad v strome v podúlohe a. má ovocie \(7\) štyri deti: \(2, 1, 8, 5\).
Ako sa dá zo zapísanej postupnosti zistiť, ktoré ovocie má koľko detí?
(30 bodov) Nie všetky stromy sú pekne pravidelné. Z akého stromu dostane Amanda postupnosť \(3, 6, 3, 4, 5, 4\)?
Podúloha A
Stačí odsimulovať ten algoritmus a dostaneme postupnosť \(7, 3, 7, 2, 7, 3, 8, 7\).
Podúloha B
Postupne odtrhneme všetky ovocia okrem koreňa (toho posledného), no a nad každým z nich je ovocie \(3\), strom teda vyzerá takto:
Podúloha C
Tu si zase môžeme všimnúť, že každé číslo od \(1\) do \(8\) sa v postupnosti nachádza práve raz, každé z týchto ovocí teda bude mať práve jedno ovocie priamo pod sebou. Úplne na spodku bude to zostávajúce ovocie, teda v tomto prípade \(9\). Strom teda bude vyzerať ako “reťaz”, kde ovocia sú postupne (zhora dole) \(4, 8, 1, 6, 3, 7, 2, 5, 9\).
Podúloha D
Každé dieťa nejakého ovocia veľkosti \(k\) odtrhneme práve raz, a práve pri týchto ovociach si zapíšeme číslo \(k\), teda každé ovocie má toľko detí, koľkokrát sa nachádza v postupnosti.
Túto úvahu sme použili aj pri minulej úlohe, kde má každé ovocie práve jedno dieťa.
Podúloha E
Tu nám môže pomôcť to, čo sme dokázali v minulej podúlohe. Vieme, koľko má každé ovocie detí, musíme ich už len poskladať dokopy tak, aby sme naozaj dostali takú postupnosť, akú chceme. S trochou skúšania sa môžeme dostať k takémuto stromu.
Ak vás toto riešenie neuspokojilo a chceli by ste nejaký všeobecný postup, ktorým strom nájdete bez skúšania, tak to si ešte budete musieť počkať - čaká vás to ako úloha v ďalšom kole :)
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ť.