2. Rebríky a Platformy

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Paulinke na [email protected]

Jedného pekného letného dňa sa Adrianka vybrala do novučičkého Parku Rebríkov a Spúšťacích Kladiek a celé hodiny skúšala rôzne rebríky, lanové dráhy a iné atrakcie. Už od príchodu so zvedavým pohľadom obdivne hľadela na najväčšiu a najkomplikovanejšiu sústavu lanorebríkov akú Park Rebríkov a Spúšťacích Kladiek mal v ponuke.

Starostlivo si vyhliadla moment, keď bol rad ku komplexu najkratší, a hneď sa do neho postavila. Rad pomaličky ubúdal a Adrianka z nudy začala analyzovať ten komplexný systém platforiem pospájaných dokopy rebríkmi z lán.

Celá preliezka sa skladala z radu za sebou idúcich platforiem umiestnených v rôznych výškach. Každé dve za sebou idúce platformi boli spojené lanorebríkom, po ktorom sa človek posúval ďalej. Tento lanorebrík buď stúpal alebo klesal v závislosti od vzájomnej výšky platforiem, ktoré spájal. Adrianka si navyše všimla veľmi zaujímavú vlastnosť – žiadne dve platfotmy neboli v rovnakej výške. V propagačnej brožúrke sa dokonca dočítala, že pre každú výšku v metroch od 1 po počet platforiem existuje platforma v danej výške.

Rad sa viac a viac skracoval a čoskoro mala na dráhu nastúpiť aj Adrianka. Zrazu si pri nástupnej plošine všimla plagát: “Uhádni výšky plošín a vyhraj!” Adrianka však pohľadom na plošiny nevedela odhadnúť ako vysoko sú. Počas presunu si teda dôkladne zapamätala aspoň to, na ktorých úsekoch dráhy stúpala, a na ktorých klesala, v nádeji, že jej to pomôže pri odhade.

Pomôžte jej zo získaných dát zistiť možné výšky platforiem!

Príklad

Ak by prvý úsek išiel dole, druhý hore a tretí opäť dole, výška platforiem (v metroch) by mohla byť 4, 1, 3, 2. Rovnako dobré by však bolo aj riešenie 2, 1, 4, 3.

Stúpanie a klesanie vieme zaznačiť schematicky: \(\uparrow\) značí stúpanie, \(\downarrow\) klesanie. Napríklad táto lanorebríková sústava sa dá zaznačiť ako \(\downarrow\uparrow\downarrow\)

Úloha

1. (2 body) Pre každú z troch zadaných postupností klesaní a stúpaní nájdite jedno možné rozloženie výšok platforiem, ktoré by mohlo zodpovedať zadanej postupnosti:
   • \(\downarrow\downarrow\uparrow\downarrow\uparrow\) (hľadáte postupnosť 6 platforiem s rôznymi výškami od 1 po 6)
   • \(\downarrow\downarrow\uparrow\uparrow\) (hľadáte postupnosť 5 platforiem s rôznymi výškami od 1 po 5)
   • \(\downarrow\downarrow\uparrow\uparrow\uparrow\uparrow\downarrow\downarrow\downarrow\uparrow\uparrow\) (hľadáte postupnosť 12 platforiem s rôznymi výškami od 1 po 12)

2. (2 body) Adrianka si povedala, že sa uspokojí aj s tým, keď nájde plošinu, ktorá by mohla byť vo výške 1. Popíšte postup, ktorý pre ľubovoľnú postupnosť stúpaní a klesaní nájde jednu pozíciu pre platformu s výškou 1. Možných pozícii môže byť viac, v takom prípade stačí ak nájdete ľubovoľnú jednu z nich.

   Vami navrhnutý postup si môžete otestovať na príkladoch z podúlohy a).

3. (4 body) Navrhnite postup, ktorý pre ľubovoľnú postupnosť stúpaní a klesaní nájde jedno možné priradenie výšok platformám, ktoré spĺňa podmienky zadania.

   Vaše riešenie má teda robiť niečo podobné ako ste vy robili v podúlohe a), preto si to na daných postupnostiach môžete vyskúšať. Pozor však na to, že musí fungovať aj pre iné, aj oveľa dlhšie postupnosti. Na overenie správnosti si môžete vytvoriť vlastné postupnosti a skúsiť to aj na nich.

4. (3 body) Na konci dráhy sa Adrianka dozvedela, že cenu útechy dostane aspoň za to, keď uhádne výšku prvej platformy. Rozmýšľa teda, koľko rôznych vyšok je pre túto platformu prípustných. Popíšte, ako by ste pre ľubovoľnú postupnosť stúpaní a klesaní určili, ako rôzne vysoko môže byť prvá platforma.

   Ak neviete ako túto podúlohu vyriešiť všeobecne, až 1 bod môžete získať ak ju vyriešite na troch konkrétnych príkladoch z podúlohy a).

5. (4 body) Adrianka sa od manažérky dráhy dozvedela, že lanová dráha je postavená tak, aby bola čo najadrenalínovejšia. To sa prejavuje tak, že na začiatok dráhy sú umiestňované čo najvyššie platformy. Ak mali návrhári dráhy viac možností (dodržiac všetky predchádzajúce podmienky vrátane dopredu stanoveného stúpania a klesania) ako umiestniť platformy, vybrali si tú, kde bola prvá platforma čo najvyššia. Ak mali stále viac možností, snažili sa maximalizovať výšku druhej, tretej atď. platformy. Inak povedané, vybrali si lexikograficky najväčšiu vyhovujúcu postupnosť.

   Adrianka je presvedčená, že s prihliadnutím na túto podmienku existuje iba jedno riešenie zhodujúce sa s dátami ktoré namerala. Pomôžte jej a navrhnite postup, ktorý pre ľubovoľnú postupnosť stúpaní a klesaní nájde najadrenalínovejšiu lanovú dráhu.

   Ako by niečo takéto vyzeralo pre postupnosť z obrázku, teda \(\downarrow\uparrow\downarrow\uparrow\)? Na prvé miesto by išla platforma výšky 4. Stále sú však prípustné dve možnosti – (4, 1, 3, 2) a (4, 2, 3, 1). Vybrať musíme tú druhú, lebo má vyššie umiestnenú druhú platformu.