Zadanie

Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy.

Stačí, že pôjdeš na stránku Programátorskej Liahne (liahen.ksp.sk). Keď budeš riešiť sadu arrays_cpp, bodmi, ktoré získaš si môžeš nahradiť riešenie tejto úlohy. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Andrejovi na ajo@ksp.sk

Dávidovi sa počas skúškového nič nechce. A už vôbec nie umývať taniere. Vždy keď niečo zje, spraví minimum námahy a tanier položí niekam vedľa seba. Občas, keď sa mu už ťažko chodí po izbe, tak nejaké taniere pozbiera a uloží ich na kopu neumytých tanierov. Ešte menej často si povie, že nejaký tanier na kope sa už časom mohol stať toxickým. Kopa neumytých tanierov medzitým poriadne narastie a on sa rozhodne, že problém trochu zmierni a umyje niekoľko najvrchnejších tanierov.

Aby vedel či už taniere treba umývať, tak si pre každý z nich pamätá jedno číslo, ktoré vyjadruje kedy naposledy bol daný tanier umytý. Dávidovi sa však nechce stále premýšľať, či má ísť už umyť taniere a aký tanier v kope je najdlhšie neumytý. Požiadal vás preto, aby ste mu na to napísali program a on už nemusel nad riadom tak intenzívne premýšľať.

Úloha

Vašou úlohou je napísať program, ktorý bude simulovať kopu neumytých tanierov. Program by mal preto vedieť spracovať 3 typy udalostí: 1. Pridanie taniera, ktorý bol naposledy umytý v čase \(x\). 2. Umytie najvrchnejšieho taniera na kope. 3. Nájdenie najtoxickejšieho, teda najdlhšie neumytého, taniera z kopy.

Formát vstupu

Na prvom riadku vstupu je jedno celé číslo \(n\) (\(1 \leq n \leq 1\,000\,000\)). Potom nasleduje \(n\) riadkov. Na každom riadku sa nachádza popis jedného príkazu. Ako sme spomínali, existujú 3 typy príkazov:

Ak ide o príkaz 1. typu, na riadku sa bude nachádzať reťazec ‘PRIDAJ x’, kde x je celé číslo a platí \(1 \leq x \leq 1\,000\,000\,000\).

Ak ide o príkaz 2. typu, na riadku sa bude nachádzať reťazec ‘UMY’.

Ak ide o príkaz 3. typu, na riadku sa bude nachádzať reťazec ‘NAJSPINAVSI’.

Formát výstupu

Pre každý príkaz 3. typu vypíšte na samostatný riadok výstupu jedno číslo. To hovorí, že najdlhšie neumytý tanier na kope bol umytý naposledy v čase \(x\). Ak sa na kope nenachádza žiadny tanier, vypíšte -1.

Hodnotenie

Vaše riešenie bude testované na 3 sadách. Rôzne sady sa budú líšiť špeciálnymi obmedzeniami:

Číslo sady 1 2 3
obmedzenie na \(n\) \(1\,000\) \(n \leq 500\,000\) žiadne
obmedzenie na \(x\) žiadne \(x \leq 1\,000\) žiadne

Príklady

Input:

7
PRIDAJ 30
NAJSPINAVSI
PRIDAJ 20
PRIDAJ 10
NAJSPINAVSI
UMY
NAJSPINAVSI

Output:

30
10
20

Na prvom riadku určíme počet príkazov, ktoré budú nasledovať – 7. Prvý príkaz pridá na kopu jeden tanier, ktorý bol umytý naposledy v čase 30. Keď sa spýtame na najšpinavší tanier v druhom príkaze, na kope sa nachádza jediný tanier s časom 30. Potom pridáme ešte 2 taniere, pričom jeden sa stane najšpinavším, ten je ale v zápätí vybraný a našpinavším sa stáva tanier s číslom 20.

Input:

6
NAJSPINAVSI
PRIDAJ 8
PRIDAJ 10
NAJSPINAVSI
UMY
UMY

Output:

-1
8

Na vstupe je 6 príkazov. Pri prvom príkaze na nájdenie najšpinavšieho taniera nie je žiadny na kope, takže vypíšeme -1. Potom pridáme dva taniere, najšpinavším sa stane tanier, ktorý bol naposledy umytý v čase 8 a potom oba taniere umyjeme.

Pri programoch, ktoré majú niečo simulovať, je vždy dobré si vyskúšať zopár príkladov vstupu a pochopiť, ako má daný program fungovať. To vedie k riešeniu, ktoré síce nie je rýchle, ale zato je určite správne. Objavený postup totiž stačí prepísať pomocou programovacieho jazyka.

Úvod do zásobnika

Pokiaľ viete čo je dátová štruktúra zásobník, môžete túto časť spokojne preskočiť.

Kopa tanierov, ktorú simulujeme sa v mnohom správa ako abstraktná dátová štruktúra s názvom zásobník. Nenechajte sa vystrašiť. Slovné spojenie abstraktná dátová štruktúra iba vyjadruje, že napriek tomu, že na uloženie informácií, napríklad čísel, používame pole a pamäť počítača, dáta máme uložené v špeciálnej, nami zvolenej forme.

Inak povedané, počítaču pripadá uloženie dát náhodné, pre nás má však hlbší zmysel. Práve to vyjadruje slovo abstrakcia. Zásobník má ako aj iné dátové štruktúry dve hlavné funkcie – vieme doň prvky (napr. čísla) pridávať a vieme z neho prvku odoberať. Obe tieto operácie však majú svoje obmedzenia. V prípade zásobníku platí, že pridávať a odoberať prvky vieme iba z vrchu zásobníka.

Predstavte si, že máte kopu tanierov. Keď nejaký špinavý pridávate, položíte ho na vrch kopy. A keď nejaký idete umyť, je asi prirodzené začať tým najvrchnejším, čím ho z vrchu kopy odoberiete. Takto funguje aj dátová štruktúra zásobník. Obmedzenie toho, ako vieme vkladať a vyberať nám dáva určitú silu. Môžete si všimnúť, že keď do zásobníka vložíme niekoľko čísel tak platí, že posledné vložené je na vrchu zásobníka. Predposledné vložené čislo je zas priamo pod vrchom zásobníka atď.

Zásobník vieme ľahko simulovať pomocou poľa. Vytvoríme si dostatočne veľké pole a jednu premennú, v ktorej si pamätáme index na miesto v zásobníku. Tento index nám ukazuje, kam si poznačiť vkladané číslo. Po jeho pridaní do poľa index zväčšíme. Pri odstraňovaní stačí naopak index iba zmenšiť.

Príklady implementácie zásobníka v jazykoch C++ a Python si môžete pozrieť tu:

Ak si chcete o zásobníku a niektorých ďalších jednoduchých dátových štruktúrach prečítať o kúsok viac, odporúčame zájsť do KSP kuchárky.

Pomalšia simulácia kopy

Ak už vieme čo zásobník je, môžeme sa pustiť do prvého riešenia. Vidíme, že naša kopa tanierov sa správa presne ako zásobník. Navyše však musíme vedieť zistiť aj to, aká je najmenšia hodnota čísel v zásobníku.

Pokiaľ máme zásobník uložený tak ako sme si spomínali vyššie, teda v poli či liste, je jednoduché pri každom príkaze typu NAJSPINAVSI prejsť týmto poľom a zistiť, aké najmenšie číslo sa v ňom nachádza. Toto riešenie nám prinesie zaslúžených 5 bodov, ale na väčšie vstupy nebude dostatočne rýchle. Dôvodom je, že pri každom takomto príkaze hľadáme minimum spomedzi všetkých čísel v zásobníku, ktorých tam môže byť časom naozaj veľmi veľa.

Rýchlejšia simulácia kopy

Tento odstavec je venovaný druhej sade, kde sú čísla, ktoré sa nachádzajú v kope resp. v zásobníku z malého rozsahu. Ako vieme tento fakt využiť pri riešení? Použijeme techniku, ktorá sa v takýchto prípadoch používa pomerne často.

Technika spočíva v tom, že si v pomocnom poli budeme na index \(i\) značiť počet čísel \(i\) v zásobníku. Zásobník bude aj naďalej fungovať rovnako, toto pomocné pole nám pomôže iba pri hľadaní najmenšieho čísla.

Keď do zásobníka pridáme číslo \(i\), zväčšíme v pomocnom poli číslo na \(i\)-tom políčku o 1, pri vyberaní zo zásobníka ho zase zmenšíme. Pri hľadaní minima nám zjavne stačí prejsť toto pomocné pole a nájsť prvé políčko, ktoré obsahuje nenulové číslo. Uvedomme si, že napriek tomu, že zásobník môže byť obrovský, naše pomocné pole je, vďaka obmedzeniu na maximálnu veľkosť čísel na vstupe, malé. Toto riešenie nám prinesie tiež 5 bodov. Implementácia popísaného riešenia môže vyzerať napríklad takto:

Kombinácia riešení

V prípade, že ste prišli na obidve vyššie spomenuté riešenia, darí sa vám získať po 5 bodov na rôznych sadách vstupov. Môžeme ich preto šikovne spojiť do jedného. V tomto riešení si opäť vytvoríme pomocné pole, do ktorého si budeme značiť počet čísel \(i\) v zásobníku a toto pole budeme používať na hľadanie najmenšieho čísla. Ak sa ale stane, že na zásobník by sme mali pridať príliš veľké číslo, prepneme náš program do druhého módu, v ktorom bude pri hľadaní minima prechádzať celý zásobník. V druhej sade takúto zmenu riešenia nespravíme, lebo čísla budú malé a v prvej sade síce budeme prechádzať celý zásobník, ale ten nemôže byť príliš veľký. Výsledkom je riešenie za 10 bodov.

Vzorové riešenie

Predstavme si, že v zásobníku sú uložené nejaké čísla a poznáme najmenšie z nich, ktoré si označíme \(x\). V prípade, že na zásobník pridáme číslo väčšie ako \(x\), minimum sa nezmenilo a môžeme pokojne pokračovať ďalej. Problém nastane iba v prípade, že na zásobník sa pridá číslo \(y\), ktoré je menšie ako \(x\). V tom prípade sa novým minimom má stať číslo \(y\). Uvedomme si však dôležitú vec. Kým bude číslo \(y\) v zásobníku, je menšie ako \(x\) a preto \(x\) minimom nebude. Ak ale \(y\) zo zásobníka odstránime, zásobník bude vyzerať rovnako, ako tesne predtým, ako sme doň \(y\) vložili. Tým pádom sa \(x\) stane opäť minimom.

Z toho vyplýva, že pri zmene minima si jeho starú hodnotu môžeme poznačiť, pretože sa nám v budúcnosti môže ešte zísť. Situácia je však o niečo komplikovanejšia. Zoberme si totiž vyššie popísaný príklad, v ktorom \(y\) nahradilo minimum \(x\) a to sme si teda niekam poznačili. Skôr ako \(y\) zo zásobníka odstránime však doň pridáme číslo \(z\), ktoré je ešte menšie ako \(y\). V tomto prípade sme v podobnej situácii. Ak sa totiž v budúcnosti stane, že \(z\) zo zásobníka odstránime, \(y\) sa opäť stane minimom a my by sme si to mali zapamätať. K číslu \(x\) si teda poznačíme aj číslo \(y\). Keď potom \(z\) odíde zo zásobníka, za nové minimum označíme posledné poznačené číslo, teda \(y\). A keď bude odstránené aj to, opäť siahneme po poslednom poznačenom čísle, teda \(x\).

V skutočnosti sa nám tu formuje druhý zásobník, do ktorého si značíme akúsi “históriu miním”. Keď pridávame do zásobníka číslo, ktoré je väčšie ako doterajšie minimum, nič sa nedeje. Ak však pridávame číslo menšie, musíme zmeniť aktuálne minimum na novú hodnotu a tú starú si zapíšeme do zásobníka miním. Pri vyberaní čísel zo zásobníka sa nič nedeje, kým neodstránime aktuálne najmenší prvok. V takom prípade sa totiž minimum musí zmeniť a my siahneme po vrchu zásobníka miním, kde na nás čaká správna hodnota, ktorú z tohto zásobníka tiež odstránime.

Takéto riešenie je v skutočnosti veľmi rýchle. Pri každej zmene zásobníka totiž nové minimum vypočítame v konštantnom čase. Buď sa totiž nezmení, alebo je prepísané pridaným číslom, alebo sa nastaví na hodnotu najvyššieho čísla v zásobníku histórie miním. Celková časová zložitosť je preto \(O(n)\). Vo vzorovej implementácii navyše používame ešte jeden trik. Najmenšie číslo si do histórie miním vkladáme po každom pridaní prvku. Vďaka tomu nemusíme kontrolovať, či odstraňované číslo je aktuálnym minimom, po vrchu historického zásobníka siahneme zakaždým. Navyše nám to s ľahkosťou vyrieši prípady, keď sa v zásobníku nachádza viacero rovnakých čísel, čo sme predtým museli špeciálne ošetrovať.

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ť.