PALMA junior
Úloha o kľúčoch od skriniek v posilňovni

Autorské riešenie
[stiahni posilnovna.py]

• Počet riešiteľov: 8 / 18 = 44 %

• Úspešnosť riešenia: 3,47 / 8 = 43,37%

Cieľom tejto úlohy bolo vybrať zákazníkovi v posilňovni také číslo skrinky, aby si s ostatnými návštevníkmi posilňovne pri prezliekaní čo najmenej prekážali. Pre zjednodušenie uvažujeme, že návštevníci odbiehajú k skrinkám aj počas cvičenia a teda chcú mať počas celého svojho pobytu v posilňovni "najvhodnejšiu" skrinku.

Jednou zo základných otázok, ktoré si pri riešení tejto úlohy musíme položiť je otázka: "Čo znamená nájsť najvhodnejšiu skrinku?". Teda určiť akési kritérium voľnosti skriniek. Intuitívne riešenie je, že najvhodnejšia skrinka sa nachádza v strede najdlhšieho úseku voľných skriniek. Obsadenosť skriniek budeme registrovať v samostatnom zozname. Index prvku v zozname reprezentuje číslo skrinky a hodnota prvku reprezentuje čas, kedy sa skrinka obsadila alebo že skrinka nie je obsadená (napr. čas 0).

Riešenie tejto úlohy môžeme rozdeliť na 3 podproblémy:

• Zistiť, či čas pobytu zákazníka v posilňovni je v čase otváracích hodín posilňovne. Ak poznáme čas príchodu zákazníka, musí platiť:

  • čas príchodu zákazníka je najskôr o 6:00 - zákazník prišiel po otvorení posilňovne

  • čas odchodu je najneskôr v čase zatvorenia posilňovne, t.j. o 22:00,
    čas odchodu = čas príchodu + 80 min (10 min prezliekanie, 60 min cvičenie a 10 min prezliekanie).

• Nájsť skrinky, ktoré sú voľné v čase príchodu zákazníka. To sú tie skrinky, ktoré boli obsadené pred viac ako 80 minútami (a teda už sú voľné) alebo v ten deň ešte neboli obsadené. Pre riešenie tohto podproblému je výhodné si vytvoriť samostatnú funkciu (najdi_volne_skrinky(skrinky, cas_prichodu)), ktorá pre každú skrinku vráti True alebo False (voľná skrinka alebo obsadená skrinka). Pre jednoduchosť preveďme všetky časové údaje na minúty.

• Určiť, ktorá z voľných skriniek je podľa kritéria voľnosti najvhodnejšia. Aj na tento podproblém je výhodné vytvoriť si samostatnú funkciu (vyber_vhodnu_skrinku(volne_skrinky)). Funkcia vráti strednú skrinku z najdlhšej súvislej postupnosti skriniek (aj je aspoň jedna voľná skrinka).

V prípade, ak sa skrinka nedá vybrať, príslušné funkcie vyhodia výnimky. To sú prípady, ak návšteva posilňovne by bola mimo otváracích hodín alebo v čase návštevy nie je žiadna skrinka voľná. Riešenie tejto úlohy môže vyzerať nasledovne: 

#Python
def najdi_volne_skrinky(skrinky, cas_prichodu):
    return [cas + 80 < cas_prichodu for cas in skrinky]


def vyber_vhodnu_skrinku(volne_skrinky):
    # index, kde konči najdlhšia súvislá postupnosť voľných skriniek
    najdlhsia_koniec = -1  
    # dĺžka najdlhšej súvislej postupnosti voľných skriniek
    najdlhsia_dlzka = 0
    # dĺžka aktualnej súvislej postupnosti voľných skriniek
    aktualna_dlzka = 0
    # zarážka na konci, aby sme nemuseli zvlášť riešiť situáciu,
    # že postupnosť končí voľnou skrinkou
    volne_skrinky.append(False)

    for index in range(len(volne_skrinky)):
        if volne_skrinky[index]:
            aktualna_dlzka += 1
        else:
            if aktualna_dlzka > najdlhsia_dlzka:
                najdlhsia_koniec = index - 1
                najdlhsia_dlzka = aktualna_dlzka
            aktualna_dlzka = 0

    if najdlhsia_koniec == -1:
        raise ValueError('Nie je voľná skrinka')

    return najdlhsia_koniec - (najdlhsia_dlzka - 1) // 2


def vrat_cislo_skrinky(skrinky, cas_prichodu_hod, cas_prichodu_min):
    # prevod času príchodu zákazníka z hodín a minút do minútového tvaru
    cas_prichodu = cas_prichodu_hod * 60 + cas_prichodu_min

    # test správnosti času príchodu
    if cas_prichodu < 6 * 60 or cas_prichodu > 22 * 60 - 80:
        raise ValueError('V čase vášho cvičenia je posilňovňa zatvorená')

    volne_skrinky = najdi_volne_skrinky(skrinky, cas_prichodu)
    vhodna_skrinka = vyber_vhodnu_skrinku(volne_skrinky)
    return vhodna_skrinka


# priklad pouzitia, program sa spusti po otovreni posilnovne 

# na zaciatku dna su vsetky skrinky volne
casy_obsadenia_skriniek = [0, 0, 0, 0, 0]

while True:
    try:
        cas = input('zadaj cas prichodu zakaznika (hod, min): ')
        cas = cas.split()
        hod = int(cas[0])
        min = int(cas[1])
        cislo_skrinky = vrat_cislo_skrinky(casy_obsadenia_skriniek, hod, min)
        print(cislo_skrinky)
        casy_obsadenia_skriniek[cislo_skrinky] = hod * 60 + min
        print(casy_obsadenia_skriniek)
    except ValueError as chyba:
        print(chyba) 

Aj keď to zadanie úlohy nevyžadovalo, doplnili sme na konci aj ukážku použitia.

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

Túto úlohu sa rozhodlo riešiť osem tímov.

Šesť tímov si túto úlohu zjednodušilo. Uvažovali tak, že zákazník prišiel v aktuálnom čase a že o všetkých skrinkách vieme len či sú, alebo nie sú obsadené. Táto interpretácia je však problematická v tom, že nevieme, kedy zákazník odíde a teda skrinka sa uvoľní. Bolo by potrebné túto funkcionalitu doplniť. Žiaľ, iba jeden tím ju s týmto zjednodušením vyriešil správne. Trom tímom sa v riešení vyskytli menšie chyby a 2 tímy svoje riešenie nedokončili.

Niektoré tímy však prišli aj na to, že najvhodnejšia skrinka je v strede najdlhšej postupnosti voľných skriniek. Jeden tím túto postupnosť voľných skriniek reprezentoval ako dva zoznamy, kde bolo pre každú skrinku zapísané, o koľko skriniek vľavo resp. vpravo je najbližšia obsadená skrinka.

Prekvapivé však je, že žiaci zabúdajú na dodržiavanie zadania. Napríklad o práci so vstupnými a výstupnými parametrami. Toto by mali mať žiaci v najvyššej kategórii už osvojené.

Špeciálne chceme pochváliť dva tímy, ktorých riešenia mali jasný cieľ, perfektne spracovaný, doslova na profesionálnej úrovni a navyše boli prehľadné a okomentované. Tím acmigtui vyriešil úlohu až na drobnú chybu úplne ukážkovo správne. Tím Šedá eminencia dodekahedrónov odovzdal taktiež ukážkové riešenie, avšak s úvahou o aktuálnom čase príchodu zákazníka.