PALMA junior
Úloha o evakuácii planéty

Autorské riešenie
[stiahni imp :py]                                       

• Počet riešiteľov: 8 / 9 = 89 %                       

• Úspešnosť riešenia: 3.81 / 8 =  47.63%                   

Keďže máme evakuovať celú planétu Turtloid, potrebujeme evakuovať všetky korytnačky. Korytnačky stoja v rade a my vieme ich hmotnosti. Prechádzame postupne zoznamom hmotností korytnačiek. Korytnačky nastupujú do pristaveného Turtleshipu, kým sa ešte zmestia. Ak sa už nejaká nezmestí, tak sa postaví na koniec radu a ďalšie sa pokúšajú nastúpiť. Ak sa dosiahne presné obsadenie Turtleshipu alebo ak už nie je žiadna korytnačka v rade taká, ktorá sa ešte zmestí, tak Turtleship odchádza. Takto budú postupne evakuované všetky korytnačky z planéty Turtloid.

Ak pre pristavený turtlesip pošleme korytnačku na koniec radu, mali by sme si poznačiť, že táto korytnačka a žiadna z tých, ktoré budú za ňou sa do tohto turtleshipu už nevojdú. Inak by sme sa ich zbytočne pokúšali naložiť do turtleshipu. Túto informáciu si môžeme poznačiť tak, že na koniec zoznamu vložíme nejaký špeciálny symbol, napr.: "x". Ak turtleship odletí, tento špeciálny symbol zo zoznamu odstránime. Pozrime sa teraz na to, ako budeme korytnačky postupne nakladať.

Kým v zozname budú nejaké prvky, vyberieme prvý prvok zo zoznamu a zisťujeme, čo treba spraviť.

• Ak je to špeciálny symbol vieme, že žiadna z korytnačiek sa už do turtleshipu nevojde. Pristavený turtleship môže odletieť a pristavíme nový.

• Ak je to hmotnosť korytnačky a jej nastúpením dosiahneme presne nosnosť turtleshipu, tak turtleship môže odletieť a pristavíme nový. Špeciálny symbol (ak bol v zozname) zo zoznamu odstránime.

• Ak je to hmotnosť korytnačky a korytnačka sa zmestí, tak nastúpi.

• Ak je to hmotnosť korytnačky, ale už sa nezmestí, postavíme ju na koniec radu. Ak v zozname ešte níe je vložený špeciálny symbol, vložíme ho tam ešte pred hmotnosť aktuálnej korytnačky.

Každý odjazd Turtleshipu si zarátavame. Ak na konci ešte ostal Turtleship, ktorý nie je ešte naplnený, no nie sú už ďalšie korytnačky, tak odchádza a zarátame ho.

def evakuacia(zoznam):
    ''' Vráti počet Turtleship-ov potrebných na evakuáciu planéty

    :param zoznam: zoznam hmotností korytnačiek stojacich v rade
    :type zoznam: list
    '''

    nosnost = 1000
    naklad = 0
    pocet_turtleshipov = 0
    pasazier_na_koniec = False

    while len(zoznam) > 0:
        pasazier = zoznam.pop(0)

        # pre tento turtleship sa pasazieri zacinaju opakovat, turtleship odchadza
        if pasazier == 'x':
            pocet_turtleshipov += 1
            pasazier_na_koniec = False
            naklad = 0

        # turtleship presne naplneny, turtleship odchadza
        elif naklad + pasazier == nosnost:
            pocet_turtleshipov += 1
            if pasazier_na_koniec:
                pasazier_na_koniec = False
                zoznam.remove('x')
            naklad = 0

        # pasazier sa vojde
        elif naklad + pasazier < nosnost:
            naklad = naklad + pasazier

        # pasazier sa nevojde, ide na koniec aj so specialnym symbolom
        else:
            if not pasazier_na_koniec:
                zoznam.append('x')
                pasazier_na_koniec = True
            zoznam.append(pasazier)

    # vsetci nastupili, ale posledny turtleship neodisiel
    if naklad != 0:
        return pocet_turtleshipov + 1

    # vsetci nastupili a posledny turtleship odisiel
    return pocet_turtleshipov

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

Zaujímavé bolo vlastne len jediné správne riešenie (tím Bojovnik Macek, kategória Expert). Riešenie veľmi elegantne a jednoducho ošetruje jednotlivé prípady, ktoré môžu pri napĺňaní turtleshipov nastať, pričom je navyše doplnené aj o textovú signalizáciu aktuálneho stavu - či došlo k plneniu/naplneniu/preplneniu turtlesipu.

V riešeniach sa vyskytli dva druhy chýb. Jeden súvisel s nie úplným pochopením zadania a neefektívnym obsadzovaním turtlesipov. Turtlesip sa napĺňal až do naplnenia jeho nosnosti a keď prišla korytnačka, ktorá by spôsobila preťaženie, turtlesip bol vyslaný preč bez toho, aby bola korytnačka presunutá na koniec radu a iné, ľahšie korytnačky, už nemohli vyskúšať dostať sa do tohto turtleship-u. Toto viedlo k vysokému počtu vyslaných turtleshipov.
Napr. pre korytnačky s hmotnosťami [700 200 200 100 800] by boli vyslané 3 turtlesipy s nasledovným obsadením [700 200] [200 100] [800] miesto dvoch s obsadením [700 200 100] [800 200].

Druhá chyba bola dôsledkom zjednodušenia riešenia, pri ktorom boli hmotnosti všetkých korytnačiek spočítané a predelené nosnosťou turtleshipov a výsledok bol zaokrúhlený nahor. Tento postup viedol k zmenšeniu počtu potrebných turtlesipov (v závislosti od hmotností jednotlivých korytnačiek) - v predošlom príklade korytnačiek s hmotnosťami [700 200 200 100 800] by sme síce získali dva potrebné turtleshipy, ale ak by sme mali korytnačky [600 450 600], tak by sme podľa tohto prepočtu potrebovali tiež len 2 turtlesipy, čo ale bohužiaľ by očakávalo rozrezanie jednej korytnačky - a naším cieľom je dopraviť celé, živé a zdravé korytnačky! Preto správny počet by bol 3 turtlesipy, keďže tieto dobre živené korytnačky nie sme schopní inak prerozdeliť do turtleship-ov.