*Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Žabovi na *

Táto úloha voľne nadväzuje na úlohu Pavúčí sklad z prechádzajúceho kola. Odporúčame si preto aspoň letmo prečítať jej zadanie aj vzorové riešenie. Na vyriešenie tejto úlohy to síce nie je nutné, myslíme si však, že vám to vie pomôcť.

Spomínate si ešte na pavúka Jonáša a jeho siete? Ukladal si do nich mušky, ktoré sa mu podarilo chytiť. Dodržiaval pri tom veľmi prísne pravidlá. Z každej mušky viedli dodola najviac dve vlákna – ľavé a pravé. Naviac, pre každú mušku v sieti platilo, že všetky mušky, ktoré boli pod ňou naľavo boli ľahšie ako ona, a všetky mušky, ktoré boli pod ňou napravo boli ťažšie ako ona. Jonášova pavučina teda mohla vyzerať napríklad takto.

Úloha

Keďže Jonáš sa chcel naučiť tkať ešte krajšie siete, vybral sa na skusi do sveta. Ako prvých navštívil svojich bratrancov v Španielsku, kde sa dozvedel, že v móde sú hlboké siete. A keďže nevedel, čo je hĺbka siete, jeho bratranci mu to vysvetlili.

Každá muška v sieti je v nejakej hĺbke. Najvyššia muška v sieti je v hĺbke 0, tie zavesené priamo pod ňou sú v hĺbke 1, tie pod nimi v hĺbke 2 atď.. Presnejšie, muška zavesená priamo pod muškou v hĺbke $x$ je v hĺbke $x+1$. Hĺbka siete je potom najväčšia hĺbka, v ktorej je ešte nejaká muška. Na obrázku vyššie teda vidíte sieť hĺbky 3.

1. (2 body) Jonáš by sa chcel pred Španielmi predviesť a čo najrýchlejšie spraviť sieť hĺbky 7. Na začiatku má prázdnu sieť, do ktorej bude postupne pridávať mušky, pričom bude celý čas dodržiavať všetky podmienky uvedené vyššie. Nájdite čo najkratšiu postupnosť mušiek, ktoré keď bude v tomto poradí pridávať do siete, dostane sieť hĺbky 7.

Pavučinu z prvého obrázku by Jonáš vytvoril, keby mušky pridával v nasledovnom poradí: 42, 29, 15, 68, 3, 35, 55, 47, 24, 30, 100¹. Pri riešení môžete použiť napríklad nasledovný nástroj btv.melezinek.cz/binary-search-tree.html. Keď vedľa tlačidla Insert (po slovensky pridaj) napíšete nejaké číslo a tlačidlo stlačíte, do stromu sa zadané číslo pridá dodržujúc všetky Jonášove podmienky.

Po Španielsku sa Jonáš vybral do Nemecka. Nemecké pavúky sú oveľa praktickejšie a snažia sa tkať svoje siete čo najplytkejšie. Komu by sa totiž chcelo behať celý deň po sieti, keď môže mať všetky mušky poruke, iba pár vlákien od vrchu.

1. (3 body) Jonáš by do svojej pavučiny rád vložil čo najviac mušiek tak, aby vzniknutá sieť mala hĺbku najviac 3. Opäť začína s prázdnou sieťou. Nájdite čo najdlhšiu postupnosť mušiek, ktoré keď bude v tomto poradí pridávať, nevytvorí sieť s hĺbkou 4.

Rovnako ako v predchádzajúcej úlohe pri riešení použite btv.melezinek.cz/binary-search-tree.html.

Jonáš sa z potuliek svetom vrátil múdrejší. Uvedomil si, že záleží na tom, ako jeho sieť vyzerá. A keďže je od prírody lenivý a za jedlom sa mu chodiť nechce, zapáčil sa mu viac nemecký spôsob stavania pavučín – čím menšia hĺbka, tým lepšie.

Keď sa však pozrel na svoju pavučinu (Obr. 2) zdala sa mu prihlboká. Hlavne vľavo bolo oveľa viac mušiek ako vpravo. Preto mu napadlo presunúť mušku 42 na vrch pavučiny. Výsledok jeho snaženia vidíte na Obr. 3. Teraz ho však zaujíma, či by takýto posun vedel robiť aj všeobecne.

1. (3 body) Navrhnite postup, ktorým bude Jonáš vedieť presunúť mušku priamo naľavo alebo napravo od najvyššej mušky na vrch pavučiny. Nezabudnite zdôvodniť, prečo je vaše riešenie správne.

Presunutím ľavej mušky dostal Jonáš z obrázku 2 obrázok 3, presunutím pravej mušky mohol zase z obrázku 3 vzniknúť obrázok 2. Dajte si pozor, že obrázok neukazuje všeobecný a ani najťažší prípad, ktorý sa Jonášovi pri presúvaní môže stať.

Ani toto Jonášovi však nestačilo. Prišiel na to, že ak by na vrch pavučiny dal mušku, ktorej váha je v strede medzi všetkými muškami, napravo aj naľavo by bolo rovnako veľa mušiek. V jeho pavučine je to muška s váhou 35, lebo práve päť mušiek je ľahších a práve päť je ťažších. Ako však dostať mušku 35 na vrch siete?

1. (3 body) Jonáš stojí pri niektorej muške v pavučine. Túto mušku by rád presunul na samý vrch pavučiny. Nechce si však pokaziť celú pavučinu a neustále musia v jeho pavučine platiť uvedené podmienky. Pomôžte mu nájsť postup, ktorý mu bude hovoriť, ako preväzovať vlákna tak, aby sa zvolená muška dostala na vrch siete. Nezabudnite, že váš postup musí fungovať pre ľubovoľnú sieť a mušku v nej, nie len pre sieť na obrázku.

Presúvanie mušiek bez konkrétneho plánu je únavné a častokrát zbytočné. Jonáš si preto nakreslil, ako má jeho pavučina vyzerať. Ostáva už len presunúť mušky v jeho sieti. Ako to však spraviť?

1. (4 body) Predstavte si, že máte dva obrázky sietí, ktoré obsahujú tie isté mušky, akurát inak usporiadané. Prvý obrázok ukazuje aktuálny stav siete, druhý ukazuje ako má sieť vyzerať. Popíšte postup, ktorý bude presúvať mušky tak, že zo siete z prvého obrázku vytvorí sieť z druhého obrázku. Samozrejme, váš postup musí fungovať na ľubovoľných dvoch sieťach s tými istými muškam.

Pri riešení môžete použiť riešenia podúlohy c) a d). Nemôžete však sieť stavať od začiatku. Dovolené máte robiť iba také zmeny, po ktorých bude sieť stále celistvá a bude spĺňať podmienky zadania. To znamená, že môžete presunúť mušku naľavo na vrch siete (ako v podúlohe c)) alebo previazať zopár vlákien, ale nemôžete povedať, že na vrch dáte mušku 27 a zvyšné mušky si zatiaľ niekam odložíte.

Ako príklad si môžete predstaviť, že Jonášova pavučina vyzerá ako na obrázku 2 a jeho cieľom je ju upraviť tak, aby vyzerala ako na obrázku 1.