5. Krkolomné oberanie

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

1. (10 bodov) Akú postupnosť by si zapísala Amanda pri jedení tohto stromu?

   

2. (20 bodov) Z nejakého stromu si Amanda zapísala postupnosť \(3, 3, 3, 3, 3, 3\). Ako mohol taký strom vyzerať?

3. (20 bodov) A ako mohol vyzerať strom, z ktorého vznikla postupnosť \(5, 2, 7, 3, 6, 1, 8, 4\)?

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í?

5. (30 bodov) Nie všetky stromy sú pekne pravidelné. Z akého stromu dostane Amanda postupnosť \(3, 6, 3, 4, 5, 4\)?