PALMA junior
Úloha o fotografovaní na rozlúčkovej party

Autorské riešenie
[stiahni : py]

• Počet riešiteľov v :  6 / 6 = 100 %                       

• Úspešnosť riešenia: 6 / 7 = 86 %                   

Podľa zadania, príchody a odchody účastníkov na party sa zaznamenávajú ako dvojprvkové zoznamy. Úlohou bolo zistiť, aký najväčší počet ludí bol naraz prítomný v jednom čase.

Úloha sa dá riešiť rôzne, uvedieme jedno z riešení.

Pre riešenie sú dôležité časové záznamy, keď niekto na párty prišiel a keď niekto z párty odišiel. Ak by sme tieto záznamy usporiadali v čase, úloha by bola jednoduchá. Postupne budeme záznamami prechádzať. Ak narazíme na záznam príchodu, zväčšime počet účastníkov. Ak narazíme na záznam odchodu, zmenšíme počet účastníkov. Zároveň si pamätáme, aký najväčši počet účastníkov sme zaznamenali.

Aby sme si nemuseli pamätať, ktorý časový údaj je záznam príchodu a ktorý je záznam odchodu, rozdelíme si časové záznamy do dvoch zoznamov. Do jedneho uložíme časy príchodov a do druhého časy odchodov. Obidva zoznamy si usporiadame

Napríklad, záznamy [[11,30],[12,30],[13,30], [1, 31] rozdelíme na príchody a odchody:

prichody: [1, 11, 12, 13]

odchody: [30, 30, 30, 31]

Funkca na rozdelenia zaznamov môžze vyzerať nasledovne:

#Python
def rozdel(zaznamy):
    '''Zoznam prichodov a odchodov rozdeli na dva zoznamy.
    Zoznam prichodov a zoznam odchodov.

    :param zaznamy: Zoznam dvojic: prichod, odchod.
    :type zaznamy: list of lists
    :return: Zoznam prichodov a zoznam odchodov
    :rtype: tuple(list, list)
    '''
    prichody = []
    odchody = []
    for zaznam in zaznamy:
        prichody.append(zaznam[0])    #pridame cas prichodu do zoznamu príchodov
        odchody.append(zaznam[1])     #pridame cas odchodu do zoznamu odchodov
    prichody.sort()                   #zoradenie prvkov zoznamov
    odchody.sort()
    return prichody, odchody

Súčasne prechádzame zoznamami príchodov a odchodov.

Ak aktuálny prvok v zozname príchodov je menší ako aktuálny prvok v zozname odchodov, niekto na párty prišiel. Zavýšime počet účastníkov a v zozname príchodov sa posunieme na ďalší prvok.

Ak aktuálny prvok v zozname odchodov je menší ako aktuálny prvok v zozname príchodov, niekto z párty odišiel. Znížime počet účastníkov a v zozname odchodov sa posunieme na ďalší prvok.

Tento postup opakujeme dovtedy, kým sa v zozname príchodov nedostaneme na koniec. Od tejto chvíle už nasledujú len odchody a počet účastníkov za bude už len znižovať.

Funkcia maximum_pritomnych() môže vyzerať takto:

# Python
def maximum_pritomnych(zaznamy):
    '''Podla zaznamu prichodov a odchodov zisti, najviac kolko ludi
    bolo na party pritomnych v jednom case

    :param zaznamy: Zoznam dvojic: prichod, odchod.
    :type zaznamy: list of lists
    :return: MňaAximalny pocet ludi pritomnych na party v jednom case,
    :rtype: int
    '''
    prichody, odchody = rozdel(zaznamy)
    max_pocet = 0  # maximálny počet prítomných v danom čase
    akt_pocet = 0  # aktuálny počet prítomných počas sledovania
    idx_prichody = 0  # index v zozname prichodov
    idx_odchody = 0  # index v zozname odchodov
    while idx_prichody < len(prichody):
        if prichody[idx_prichody] <= odchody[
            # ak nastal prichod, zvysime pocet ludi na party
            idx_odchody]:
            akt_pocet = akt_pocet + 1
            if akt_pocet > max_pocet:
                max_pocet = akt_pocet
            idx_prichody = idx_prichody + 1
        else:
            # ak nastal odchod, znizime pocet ludi na party
            akt_pocet = akt_pocet - 1
            idx_odchody = idx_odchody + 1
    return max_pocet

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

Úlohu väčšina z Vás riešila pomocou dvoch, alebo aj troch cyklov, postupne ste prechádzali zoznamom príchodov a pomocou vnoreného cyklu ste testovali odchody, čím ste dosiahli správny výsledok, ale nie sú to efektívne riešenia.

Niektorí ste testovali aj to, či zadané vstupy sú správne, teda čas príchodu nie je väčší ako čas odchodu. V zadaní síce bolo stanovené, že vstupy sú vhodne zadané, ale z programátorského hľadiska je korektné aj to testovať.

Pozitívne hodnotíme aj to, ak premenné ste pomenovali tak, aby význam názvu priamo naznačil obsah.