PALMA junior
Úloha o správnom poradí v rade

Autorské riešenie
[stiahni py]

• Počet riešiteľov: 17 / 23 = 73.91 %

• Úspešnosť riešenia: 3,11 / 7 = 44 %

V tejto úlohe musíme vyriešiť, ako správne zaraďovať prichádzajúce korytnačky do zoznamu korytnačiek, ktoré už v zozname sú. Zohľadniť musíme dve kritériá:

1. primárne kritérium je čas, na ktorý je korytnačka objednaná,

2. sekundárne kritérium je poradie, v akom korytnačky prichádzajú pred úrad.

To znamená, že ak korytnačku zaraďujeme do zoznamu, najskôr si všímame čas, na ktorý je objednaná. Ak v zozname už sú nejaké korytnačky s rovnakým časom, uplatníme druhé kritérium - čas príchodu.

Celý postup zaraďovania korytnačky na správne miesto do zoznamu môžeme rozpísať nasledovne:

1. Nájdime v zozname miesto, kde sa nachádza skupinka korytnačiek objednaná na rovnaký čas. Stačí, ak nájdeme jednu takúto korytnačku, pretože ostatné s rovnakým časom budú pred ňou alebo za ňou.

   • Ak sme takúto skupinku našli, nájdime, kto je v nej posledný. Za neho vložíme novú prichádzajúci korytnačku.

   • Ak v zozname čakajúcich nie je nikto s rovnakým časom, nájdime miesto, kam prichádzajúcu korytnačku zaradiť. Je to miesto, kde jedným smerom je korytnačka s menším časom a druhým smerom korytnačka s väčším časom. Nezabudnime, že môže nastať aj situácia, keď novú korytnačku zaradíme na začiatok (ostatné korytnačky sú objednané na neskorší čas) alebo na koniec (ostatné korytnačky sú objednané na skorší čas).

2. Vložíme korytnačku na nájdené miesto.

Schéma riešenia môže vyzerať nasledovne:

# Python
def registruj(zoznam, casovy_listok):
    pozicia = pozicia_cas(zoznam, casovy_listok)
    zoznam.insert(pozicia, casovy_listok)

Pozrime sa bližšie na to, ako nájsť miesto - pozíciu, kam zaradiť prichádzajúcu korytnačku. Prirodzene nás napadne začať na jednom konci zoznamu a pokračovať k jeho druhému koncu kým nenájdeme hľadanú pozíciu. Je to iste správna úvaha i keď tento postup nie je veľmi efektívny. Nijako nevyužívame fakt, že korytnačky sú v zozname už usporiadané. Tento fakt môžeme využiť a skupinu s rovnakým časom nájsť rýchlejšie.

Predpokladajme situáciu ako na obrázku nižšie. Zelenou sú označené tie korytnačky v rade, ktorých čas objednania je skorší. Modrou sú označené korytnačky s rovnakým časom a červenou korytnačky s neskorším časom objednania.

1. Označme si prvú a poslednú pozíciu v prehľadávanom úseku zoznamu (ľavý, pravý). Na začiatku je prehľadávaným úsekom celý zoznam. Ak by tento úsek bol prázdny, našli sme hľadané miesto.

2. Pozrime sa, aký čas má korytnačka v strede prehľadávaného úseku.

   • Ak je jej čas objednania rovnaký, našli sme skupinku korytnačiek s rovnakým časom a môžeme skončiť.

   • Ak je jej čas objednania skorší, stačí ďalej prehľadávať len úsek za ňou. Pokračujme bodom 1.

   • Ak je jej čas objednania neskorší, stačí ďalej prehľadávať len úsek pred ňou. Pokračujme bodom 1.

Ak sme prehľadávanie ukončili, nastať mohli dve situácie:

Ak sa v zozname nachádzajú nejaké korytnačky s rovnakým časom, skončili sme na pozícii niektorej z nich. Miesto kam zaradiť novú korytnačku je na konci tejto skupiny korytnačiek.

Ak sa v zozname nenachádzajú nejaké korytnačky s rovnakým časom, skončili sme na pozícii, kam novú korytnačku môžeme priamo zaradiť.

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

# Python
def cas(casovy_listok):
    pozicia_dvojbodky = casovy_listok.index(':')
    vysledok = casovy_listok[pozicia_dvojbodky + 1:]
    return vysledok

def pozicia_cas(zoznam, casovy_listok):
    lavy = 0
    pravy = len(zoznam) - 1
    while lavy <= pravy:
        stred = (lavy + pravy) // 2
        if cas(zoznam[stred]) == cas(casovy_listok):
            return stred
        elif cas(zoznam[stred]) < cas(casovy_listok):
            lavy = stred + 1
        else:
            pravy = stred - 1
    return lavy

def registruj(zoznam, casovy_listok):
    pozicia = pozicia_cas(zoznam, casovy_listok)
    while pozicia < len(zoznam) and cas(casovy_listok) == cas(zoznam[pozicia]):
        pozicia = pozicia + 1
    zoznam.insert(pozicia, casovy_listok)

Na nájdenie pozície sme si vytvorili funkciu pozicia_cas. Aby sa nám ľahšie porovnávali časové lístky, vytvorili sme si funkciu cas, ktorá zo záznamu na časovom lístku vyberie len časový údaj. Vo funkcii registruj po nájdení pozície (nejaká korytnačka s rovnakým časom ako práve prichádzajúca), nájdeme pozíciu za skupinkou korytnačiek s rovnakým časom. Tam vložíme novú korytnačku.

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

Najväčší problém vám spôsobilo nájdenie správnej pozície, kam v zozname zaradiť prichádzajúcu korytnačku. Len niekoľko z vás uvažovalo o binárnom vyhľadávaní. Komplikovane ste riešili porovnávanie časových údajov, ktoré ste zbytočne "rozbíjali" na jednotlivé časové jednotky. To nebolo potrebné, lebo časy sa dali priamo porovnať.

Zaujímavú myšlienku sme našli v tíme srobarkaMJ guru. Korytnačky s rovnakým časom by boli v jednom zozname. Celý zoznam by bol ako hodnota v slovníku, kde kľúčom je časový údaj. Toto riešenie je efektívne pri samotnom zaraďovaní prichádzajúcej korytnačky. Nevýhoda sa prejaví, ak nejakú korytnačku pošleme z radu do vnútra úradu. V tomto prípade je potrebné kľúče v slovníku usporiadať (aby sme našli tie s najskorším časom) a ošetriť stav, keď korytnačka s týmto časom je v rade posledná (je potrebne tento kľúč zo slovníka odstrániť). Pri odoberaní korytnačiek toto riešenie nie je veľmi efektívne. Samotné odoberanie korytnačiek z radu sme však v tejto úlohe neriešili.