PALMA junior
Úloha o výške rýchlorastúceho bambusu

Autorské riešenie
[stiahni py]

• Počet riešiteľov: 9 / 13 = 69 %

• Úspešnosť riešenia: 5.4 / 7 = 77 %

Ak máme odpovedať na otázku, akú výšku mal alebo bude mať bambus v nejaký deň svojho života, musíme zohľadniť dve veci:

• bambus nepretržite rastie, každý deň podrastie do výšky o 1 cm,

• bambus záhradníci strihajú, takže jeho výška je priebežne skracovaná.

Jedným z riešení tejto úlohy je simulovať rast bambusu, pričom budeme zohľadňovať aj jednotlivé strihania. Ak vieme, aká by mala byť výška bambusu v deň strihania, vieme povedať aj to, aká je po zostrihnutí. Simuláciu nemusíme robiť pre každý deň (vieme, že každý deň podrastie o 1 cm). Stačí simulovať výšku bambusu v dni, keď do rastu nejako zasiahneme, t.j. v dni strihania.

Nezabudnime na prípady, ak by záhradník chcel skrátiť výšku bambusu o viac než je jeho celková výška. Keďže nevieme nič o tom, ako sa robot v danej situácii zachová, môžeme uvažovať dve reakcie a nasledovné riešenia:

• takýto záznam vyhlásime za chybný a

  • budeme ho ignorovať a ostatné záznamy spracujeme,

alebo

• skončíme so správou, že záznam je chybný

alebo

• dĺžku skrátime na 0.

Vo vašich riešeniach sme akceptovali ako správny každý z uvedených prístupov.

Pozrime sa, ako by sa menila výška bambusu, ak by sme mali napríklad takýto záznam o strihaniach
[[5, 3], [11, 10]] a chceli vedieť výšku bambusu na 16. deň. Uvažujme prípad, keď pri pokuse o nadmerné skrátenie bambusu ho skrátime na 0.

V 0. deň sme bambus zasadili a jeho výška je teda 0 cm. V 5. deň by výška mala byť 5 cm. Keďže sme ho zostrihli o 3 cm, bude jeho výška len 2 cm. V 11. deň by mal bambus narásť do výšky 8 cm. Pokúsili sme sa ho zostrihnúť o 10 cm. Výsledkom je výška 0. Do 16. dňa bambus nerušene rastie a jeho výška v tento deň dosiahne 5 cm.

Výsledné riešenie môže vyzerať nasledovne:

# Python
def vyska_bambusu(zaznamy, den):
    # nastavíme počiatočné hodnoty simulacie, v deň 0 je výška bambusu 0 cm
    vyska = 0
    den_zasahu = 0
    # test, ak chceme vedieť výšku pred zasadením
    if den <= 0:
        return 0
    # postupne prechádzame jednotlivé záznamy o strihaní
    for zaznam in zaznamy:
        # otestujeme prípad, keď nás zaujúma den medzi dvoma strihaniami
        if den < zaznam[0]:
            return vyska + den - den_zasahu
        #k výške bambusu pripočítame to, čo narástol od posledného strihania
        vyska = vyska + zaznam[0] - den_zasahu
        den_zasahu = zaznam[0]
        # od výšky bambusu odpočítame o koľko ho robot skrátil
        vyska = vyska - zaznam[1]
        # ošetrime prípad, ak by po skrátení mala byť výška záporná
        if vyska < 0:
            vyska = 0
    return vyska + den - den_zasahu

V tomto riešení sme pokus o nadmerné skrátenie bambusu (viac ako je jeho aktuálna dĺžka) vyriešili tak, že sme dĺžku upravili na 0.

V premennej vyska registrujeme aktuálnu výšku bambusu počas simulácie jeho rastu. Na začiatku je to 0 cm. V premennej den_zasahu si pamätáme ostatný deň, kedy sme do rastu bambusu nejako zasiahli (zasadili sme ho alebo ho zostrihli). Na začiatku je týmto dňom deň 0.

Ošetrili sme aj situáciu, ak by sme chceli vedieť výšku bambusu pred jeho zasadením. V takomto prípade bude jeho výška 0. 

Postupne prechádzame záznamy o strihaniach a pre každý záznam upravíme výšku bambusu. Testujeme, či sme ešte neprekročili deň, v ktorý nás výška zaujíma. Ak áno, vrátime výšku zväčšenú o nárast od posledného zásahu. V opačnom prípade upravíme výšku bambusu a aktualizujeme premenné vyska a den_zasahu.

Ak sme spracovali všetky záznamy o strihaniach, vrátime výšku upravenú o nárast od posledného zásahu.

Vaše zaujímavé riešenia a najčastejšie chyby

Až na pár prípadov ste úlohu riešili správne. Niektorí z vás zabudli uvažovať o prípade, ak sa pokúsime bambus skrátiť o viac ako je jeho dĺžka. V týchto prípadoch funkcia odpovedala zápornou výslednou dĺžkou. Viacerí z vás neefektívne simulovali rast bambusu. Buď ste použili dva cykly v sebe alebo ste vypočítavali výšku bambusu pre každý deň jeho rastu.