PALMA junior, Programovanie, ALgoritmy, MAtematika, súťaž pre mladých programátorov v Pythone

	PALMA junior

Úloha o sezóne v kempe

Autorské riešenie
[stiahni py]

Počet riešiteľov: 28/33 = 85 %
Úspešnosť riešenia: 4,05 / 6 = 67,56 %

Pri riešení tejto úlohy nám pomôže rozbor konkrétneho prípadu a jeho grafické zobrazenie. Uvažujme konkrétny prípad 4 návštevníkov, ktorých príchody a odchody sú zaznamenané v zozname [1, 9, 3, 6, 4, 8, 7, 9]. Túto situáciu vieme reprezentovať graficky pomocou úsečiek a číselnej osi. Pri riešení úlohy nám stačí preskúmať príchody a odchody všetkých návštevníkov. Pri príchode každého účastníka zvýšime počet návštevníkov o 1 a pri jeho odchode znížime počet návštevníkov o 1. V priebehu výpočtu zisťujeme či aktuálny počet návštevníkov prekročil maximálnu hodnotu.

Kemp

Tento konkrétny prípad využijeme pri nasledovnom všeobecnom riešení. Do jedného pomocného zoznamu si uložíme príchody a do druhého odchody návštevníkov. Po usporadaní týchto zoznamov prechádzame oboma zoznamami, a to tak, že ak hodnota daného príchodu je menšia ako hodnota odchodu, tak zvýšime o 1 počet návštevníkov a posunieme sa v zozname príchodoch o 1 miesto ďalej. V opačnom prípade znížime o 1 počet návštevníkov a posunieme sa v zozname odchodov o 1 miesto.

Výsledné riešenie úlohy zapísané v programovacom jazyku Python môže vyzerať nasledovne

def max_navstevnost(zaznamy):
    ''' Vráti maximálnu dennú návštevnosť kempu '''
    prichody = zaznamy[::2]
    odchody = zaznamy[1::2]
    prichody.sort()
    odchody.sort()
    pocet = 0
    maxpocet = 0
    idx_prichod = 0
    idx_odchod = 0
    while idx_prichod < len(prichody) and idx_odchod < len(odchody):
        if prichody[idx_prichod] < odchody[idx_odchod]:
            idx_prichod = idx_prichod + 1
            pocet = pocet + 1
        else:
            idx_odchod = idx_odchod + 1
            pocet = pocet - 1
        if pocet > maxpocet:
            maxpocet = pocet
    return maxpocet

Táto úloha je zameraná na:

použitie rôznych stratégii riešenia problémov (dekompozície problému na podproblémy, vykreslenie obrázka),
precvičenie príkazov opakovania s podmienkou, volania funkcií s parametrom a výstupom, príkazov vetvenia, prácu s dátovým typom zoznam.

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

Do riešenia tejto úlohy sa zapojilo 11 tímov z kategórie EXPERT a 17 tímov kategórie GURU. Plný počet bodov dosiahol len tím seesharp guru, ktorému gratulujeme.

Súťažiaci pri riešení použili rôzne typy vstupov:

jednoduchý zoznam s príchodmi na párnych a odchodmi na nepárnych pozíciách,
zoznam dvojprvkových zoznamov s príchodom a odchodom,
dva zoznamy - zoznam príchodov a zoznam odchodov,
textový reťazec s dvomi typmi oddeľovačov (čiarkou medzi príchodom a odchodom, bodkočiarkou medzi údajmi návštevníkov).

Zopár súťažiacich okrem vypočítania maximálnej dennej návštevnosti bonusovo uviedla aj zoznam dní, v ktorých bola táto návštevnosť dosiahnutá.

Štyria súťažiaci použili pri výpočte dátový typ slovník (angl. dictionary).

V riešeniach sme zaregistrovali nasledovné nedostatky, vychádzajúce najčastejšie z nedôslednej analýzy problému, tvorby menej efektívneho riešenia či z pretrvávajúcich programátorských zlozvykov:

neefektívne riešenie s použitím pomocného zoznamu (s 365, 366, resp. 367 prvkami, resp. zoznam, ktorého veľkosť závisela od minimálnej a mazimálnej hodnoty zoznamu príchodov a odchodov),
namiesto použitia funkcií s parametrami použitie globálnych premenných s príkazom input a funkciami bez parametrov,
zbytočné používanie príkazov print vo funkciách, na vynesenie výslednej hodnoty z funkcie treba použiť príkaz return,
namiesto plnovýznamových identifikátorov premenných použitie málohovoriacich jednopísmenových identifikátorov.

PALMA junior

Úloha o sezóne v kempe