Zadanie

Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš koľko si dostal/a bodov. Ak si takýto typ úloh ešte nikdy neriešil/a skús sa pozrieť ako by mal vyzerať ideálny program. Ak zatiaľ programovať nevieš, ale chcel/a by si vedieť možeš skúsiť náš python tutoriál.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Miške na email [email protected]

Škola je v plnom prúde a Mišku so Sofi čaká testík z nemeckých nepravidelných slovies. Ani jedna z nich nevie nemčinu, a tak sa dohodli, že sa po vyučovaní pôjdu spolu učiť. Nemôžu sa ale začať učiť, kým nebudú mať spravený absolútne dokonalý playlist, kde sú pesničky vhodné na takúto príležitosť! Na vytvorenie tohto playlistu chcú použiť aplikáciu so všetkými funkciami, ktoré považujú za nevyhnutné. Chcú postupne pridávať, počúvať a preskakovať pesničky. Väčšina aplikácii toto zvláda, avšak posledná nevyhnutná funkcia je ukazovanie koľko času zostáva do konca playlistu. Všetky aplikácie ukazujú celkový čas playlistu, ale po vypočutí a preskočení niektorých pesničiek ich zaujíma, koľko času zostáva do konca. Nešťastné z tejto skutočnosti zistili, že ich jediné riešenie je si aplikáciu naprogramovať. Lenže, Miška a Sofi nemajú čas na programovanie, pretože sa musia učiť, a tak sa obrátili na vás, aby ste to spravili za nich.

Úloha

Na vstupe dostanete kombinácie štyroch príkazov označených číslami od \(1\) po \(4\). Vašim cieľom je príkazy postupne spracovávať a vyhodnocovať. Význam príkazov je nasledovný:

  1. pridajte pesničku dĺžky \(t\) sekúnd na koniec playlistu.
  2. prešlo \(t\) sekúnd.
  3. preskočte práve aktívnu pesničku.
  4. vypíšte koľko sekúnd ostáva do konca playlistu.

Môžete predpokladať, že nebudete preskakovať pesničku pokiaľ je playlist prázdny a že \(t\) nikdy nebude viac ako čas ostávajúci do konca playlistu.

Formát vstupu

Na prvom riadku dostanete číslo \(n\), počet príkazov. Na nasledujúcich \(n\) riadkoch sa nachádza na každom riadku jeden príkaz (číslo od \(1\) po \(4\)). Za príkazom \(1\) a \(2\) nasleduje v tom istom riadku číslo udávajúce počet sekúnd \(t\).

Formát výstupu

Po každom príkaze \(4\) vypíšte jedno číslo udávajúce koľko sekúnd ostáva do konca playlistu.

Hodnotenie

Existuje \(5\) sád vstupov. Za každú správne vyriešenú sadu získate \(20\) bodov. Dĺžky pesničiek nepresiahnu 300 sekúnd. Pre jednotlivé sady vstupov platia nasledovné obmedzenia:

Sada. 1. 2. 3. 4. 5.
\(1 \leq n \leq\) \(10\) \(1\ 000\) \(50\ 000\) \(100\ 000\) \(300\ 000\)

Príklad

Input:

3
1 100
2 42
4

Output:

58

Príkaz číslo 1 pridá pesničku dĺžky 100 sekúnd, do konca playlistu teda ostáva 100 sekúnd. Nasleduje príkaz 2 ktorý hovorí že prešlo 42 sekúnd a do konca playlistu teraz ostáva \(100 - 42 = 58\) sekúnd. Nakoniec vypíšeme koľko sekúnd ostáva do konca playlistu, čo je teda 58 sekúnd.

Input:

6
1 72
1 45
4
3
2 12
4

Output:

117
33

Pridáme pesničky dĺžky 72 a 45 sekúnd, do konca playlistu ostáva \(72 + 45 = 117\) sekúnd. Vypíšeme koľko času ostáva do konca. Príkazom 3 je preskočená aktívna pesnička, v playliste ostáva pesnička o dĺžky 45 sekúnd. Prejde 12 sekúnd a vypíšeme čas čo ostáva do konca, čo je 33 sekúnd.

Úplne prvé, čo by nám malo napadnúť je, že všetky dĺžky pesničiek si chceme ukladať do nejakého zoznamu. Pre každý príkaz vymyslíme, ako sa s ním vysporiadame: 1. Pridanie pesničky dĺžky \(t\) do playlistu je to isté, ako keď si premennú \(t\) uložíme do zoznamu. 2. Preskočenie pesničky môžeme vyriešiť rôznymi spôsobmi. Najjednoduchší spôsob je vymazanie prvého prvku zoznamu. Toto však môže byť v Pythone veľmi pomalé, ak použijeme nesprávny zoznam. Pomalý zoznam je napríklad list a rýchly zoznam je napríklad dequeue. Ďalší spôsob je pamätanie si indexu aktuálnej pesničky bez toho aby sme čokoľvek vymazali zo zoznamu. Toto nám vyriešia dve čísla \(x\) a \(y\), ktoré nám povedia, na ktorej pesničke momentálne sme a koľko sekúnd z nej prešlo. 3. Prešiel daný počet sekúnd – začneme od aktuálnej pesničky, ktorá je buď prvá v zozname, alebo je na indexe, ktorý si pamätáme v premennej (podľa toho či odstraňujeme prvky alebo nie). Môžu nastať dve situácie: - Počet sekúnd, ktoré preskakujeme je menší ako dĺžka aktuálnej pesničky. V tom prípade odčítame od aktuálnej pesničky počet sekúnd (zmeníme číslo v zozname). - Počet sekúnd, ktoré preskakujeme je viac ako dĺžka aktuálnej pesničky. V tomto prípade odčítame dĺžku aktuálnej pesničku od počtu sekúnd ktoré preskakujeme a pesničku vymažeme (alebo zväčšíme index) a znova zopakujeme. 4. Vypísanie času, ktorý ostáva do konca môžeme riešiť rôzne. Pomalé riešenie a zároveň to najviac triviálne by vyzeralo tak, že zakaždým prejdeme cez celý zoznam for cyklom a spočítame zostávajúci počet sekúnd. To je ale neefektívne a pri veľkých vstupoch to nebude stíhať. Rýchle riešenie je, že si aktuálny počet sekúnd do konca budeme pamätať v jednej premennej, ktorú si po každom príkaze aktualizujeme a pri príkaze 4 vypíšeme.

Časová a pamäťová zložitosť

Každá okrem štvrtej operácie buď pridá jeden prvok do zoznamu, alebo ich niekoľko vymaže a okrem toho spraví nejaké výpočty. Celkovo teda vykonajú približne dva krát toľko operácií ako bude pesničiek. Pesničiek určite nebude viac ako \(n\) a preto je časová zložitosť \(O(n)\) aj napriek tomu že jedna operácia môže znamenať postupné vymazanie clej fronty. Pamäťová zložitosť je tiež \(O(n)\), pretože vo fronte nemôže byť viac ako \(n\) pesničiek.

Listing programu v Pythone:

from collections import deque

n = int(input())

playlist = deque()
ostavajuci_cas = 0

for _ in range(n):
    prikaz = [int(x) for x in input().split()]

    # pridanie pesnicky
    if prikaz[0] == 1:

        d = prikaz[1]
        ostavajuci_cas += d
        playlist.append(d)

    # presiel cas
    elif prikaz[0] == 2:

        t = prikaz[1]
        ostavajuci_cas -= t

        while playlist and t >= playlist[0]:
            t -= playlist[0]
            playlist.popleft()

        if playlist:
            playlist[0] -= t
    # preskocenie pesnicky
    elif prikaz[0] == 3:

        ostavajuci_cas -= playlist[0]
        playlist.popleft()

    # vypisanie casu
    else:
        print(ostavajuci_cas)

A takto môže vyzerať v C++:

#include <queue>
#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int ostavajuci_cas = 0; // dlzka playlistu do konca
    queue<int> pesnicky; // playlist

    for (int i = 0; i < n; i++)
    {
        int prikaz;
        cin >> prikaz;

        if (prikaz == 1)
        {
            int d;
            cin >> d;

            ostavajuci_cas += d;
            pesnicky.push(d);
        }
        else if (prikaz == 2)
        {
            int t;
            cin >> t;

            while (pesnicky.size() > 0 && t >= pesnicky.front())
            {
                ostavajuci_cas -= pesnicky.front();
                t -= pesnicky.front();
                pesnicky.pop();
            }
            ostavajuci_cas -= t;
            if (pesnicky.size() > 0)
                pesnicky.front() -= t;
        }
        else if (prikaz == 3)
        {
            ostavajuci_cas -= pesnicky.front();
            pesnicky.pop();
        }
        else if (prikaz == 4)
        {
            cout << ostavajuci_cas << endl;
        }
    }

    return 0;
}

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.