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 Liahni (liahen.ksp.sk). Keď budeš riešiť sadu variables_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 Žabovi na zaba@ksp.sk

Jeden z príznakov toho, že chodíte na veľa informatických súťaží, je, že sa vám začnú hromadiť tričká. A Žabovi sa mu ich za tie roky nahromadilo vskutku neúrekom. Teraz ich má uložené v skrini na jednej veľkej kope. Problémom ale je, že Žaba nemá rád zmenu. Keď si teda ráno vyberá, ktoré tričko si dá na seba, zoberie vždy to, čo je navrchu. A večer ho dá do svojej ultramodernej práčky a sušičky v jednom, ktorá mu ho expresne operie a on si ho opäť položí na vrch kopy.

Lucka sa už nemohla pozerať na to, ako Žaba chodí stále v tom istom tričku. Ráno mu preto prikázala, aby si obliekol tričko, ktoré mal na sebe oblečené najmenší počet krát. A keďže takých bolo v kope viacero, zobral to, ktoré bolo najvyššie (t.j. najbližšie pri vrchu). Svoje ďalšie zvyky však Žaba nezmenil – keď večer prišiel domov, tričko opral a hodil na vrch kopy. A tak sa po pár dňoch aj toto nové tričko stalo okukaným.

Lucka mu preto vždy raz za čas povedala, aby si zobral nové tričko a Žaba jej želanie naplnil – teda zakaždým z kopy vytiahol tričko, ktoré mal na sebe dovtedy oblečené najmenejkrát (a v prípade rovnosti to z nich, ktoré bolo nabližšie k vrchu kopy). A keď mu nič nepovedala, tak použil svoj starý prístup a proste zobral tričko, ktoré bolo navrchu. Lucka má teraz problém sa k Žabovi zladiť, preto by potrebovala pomôcť. Vedeli by ste jej povedať, ktoré tričko bude mať Žaba kedy oblečené?

Úloha

Žaba má \(n\) tričiek. Všetky tričká sú uložené na jednej veľkej kope, postupne jedno na druhom. Na začiatku sú očíslované od 1 po \(n\) v poradí zhora nadol – teda tričko 1 je na vrchu kopy, pod ním je tričko 2, a tak ďalej, až po tričko \(n\) úplne na spodku. Pre každé tričko poznáte hodnotu \(t_i\), ktorá označuje, koľkokrát ho už Žaba mal oblečené.

Vašou úlohou bude pre nasledujúcich \(q\) dní zistiť, ktoré tričko bude mať Žaba oblečené. Pritom viete, či si v daný deň zoberie tričko z vrchu kopy, alebo nájde najvyššie tričko v kope, ktoré mal oblečené najmenší počet krát.

Pamätajte na to, že po každom dni si Žaba dané tričko vyperie a položí na vrch kopy, pričom počet nosení tohto trička sa zvýši o jedna.

Formát vstupu

Na prvom riadku vstupu sú dve čísla \(n\) a \(q\) – počet tričiek na kope a počet najbližších dní, ktoré Lucku zaujímajú.

Na druhom riadku vstupu je \(n\) medzerami oddelených čísel \(t_1, t_2 \dots t_n\). Hodnota \(t_i\) označuje, koľkokrát mal Žaba už oblečené tričko \(i\).

Nasleduje \(q\) riadkov. Na každom z nich je jeden znak – Z alebo L – určujúci rozhodnutie, ktoré v daný deň Žaba spraví. Ak je na vstupe Z, Žaba si zoberie najvrchnejšie tričko kopy. Ak je na vstupe L, vyberie si to tričko, ktoré mal na sebe najmenší počet krát. V prípade, že je takýchto tričiek viac, vyberie si to, ktoré je v kope najvyššíe.

Formát výstupu

Pre každý z \(q\) dní vypíšte na samostatný riadok číslo trička, ktoré si v ten deň Žaba oblečie.

Hodnotenie

Vaše riešenie bude testované iba na 5 rôznych vstupoch. Za každý vstup, na ktorý odpovie váš program správne získate 3 body.

V prvých dvoch vstupoch platí, že \(n = 1\,000\) a \(q = 5\,000\).

V zvyšných troch je \(n = 100\,000\) a \(q = 500\,000\).

V treťom vstupe môžete navyše predpokladať, že počas všetkých dní platí, že rozdiel najväčšieho a najmenšieho počtu nosení niektorého trička nepresiahne 2.

Vo všetkých vstupoch platí, že začiatočné hodnoty nosení \(t_i\) nepresiahnu \(1\,000\,000\).

Príklady

Input:

5 7
2 3 2 4 2
Z
L
Z
L
L
Z
L

Output:

1
3
3
5
5
5
1

Prvý deň si Žaba oblečie tričko z vrchu kopy, teda tričko s číslom 1. Na druhý deň si má obliecť tričko s najmenším počtom nosení. Také sú v kope dve, číslo 3 a 5, vyššie z nich je však tričko 3, preto si ho oblečie a dá na vrch kopy. Tretí deň opäť zoberie toto tričko zvrchu kopy, tričko číslo 3 teda bolo nosené už štyri dni. Na štvrtý deň je tričko s najmenším počtom nosení tričko číslo 5, Žaba si ho preto oblečie. Piaty deň si má opäť vybrať tričko, ktoré mal na sebe najmenší počet krát. V tomto prípade má na výber tričká 1, 2 a 5. Najvyššie z nich, a zrovna na vrchu kopy, je tričko číslo 5, preto si ho oblečie. Na šiesty deň svoju voľbu zopakuje a v posledný deň si vyberie vyššie z dvoch tričiek, ktoré mal na sebe iba trikrát – tričko číslo 1.

V našom prvom riešení využijeme, že počty nosení tričiek sú rozumne malé (neprevyšujú \(10^6\)). Namiesto jednej obrovskej kopy si spravíme veľa menších kôp: pre každé \(x\) si spravíme kopu, na ktorej budú všetky tričká, ktoré mal Žaba zatiaľ na sebe presne \(x\)-krát. Na začiatku tam tričká rozmiestnime tak, aby ich poradie zhora dole zodpovedalo poradiu zhora dole v pôvodnej kope.

Navyše si ešte spravíme jednu pomocnú premennú, v ktorej si budeme pamätať, ktoré tričko je práve na vrchu celej kopy.

Ako bude vyzerať deň podľa Lucky? Ráno Žaba nájde najmenšie \(x\), ktorému zodpovedá neprázdna kopa tričiek. Z tejto kopy si zoberie vrchné tričko – teda to, ktoré bolo najbližšie k vrchu pôvodnej kopy. No a keď ho večer operie a usuší, položí ho na vrch kopy s číslom \(x+1\). (Všimnite si, že aj po tomto úkone platí, že tričká na kôpke \(x+1\) sú uložené v tom poradí, v ktorom by v skutočnosti boli v pôvodnej kope – práve nosené tričko totiž šlo na vrch úplne celej pôvodnej kopy.) No a na záver si už len práve donosené tričko uložíme do premennej pre vrch kopy.

A ako bude vyzerať deň podľa Žabu? Jeho spôsob vyberania trička sa simuluje ľahko: stačí sa pozrieť do pomocnej premennej na tričko na vrchu kopy. Potom, ako ho donosí, ho však nesmieme zabudnúť presunúť – teda ak doteraz bolo na kôpke pre \(y\) nosení, odteraz bude na kôpke pre \(y+1\).

Na záver zopár implementačných detailov: * Keďže žiadnemu tričku počet nosení nemôže ubudnúť, nemusí Žaba hľadať najmenšiu neprázdnu kopu vždy odznova. Namiesto toho môžeme šikovne využiť, že ak naposledy bral tričko z kôpky \(x\), najbližšie ho bude brať z kôpky s číslom aspoň \(x\). * Na zapamätanie kôpky nám stačí ľubovoľná dátová štruktúra, z ktorej vieme na jednom konci efektívne vyberať prvky a aj na ten istý koniec nové vkladať. Základnou takouto štruktúrou je zásobník. Môžeme však použiť aj všeobecnejšie dátové štruktúry (ako napr. vector v C++, ArrayList v Jave, prípadne list v Pythone). * Pri šikovnej implementácii dostávame časovú zložitosť \(O(n+q+m)\), kde \(n\) je počet tričiek, \(q\) je počet dní, ktoré treba odsimulovať, a \(m=\max t_i\) je najväčší počet oblečení trička doteraz.

N, Q = [ int(_) for _ in input().split() ]
T = [ int(_) for _ in input().split() ]
M = max(T)
T = [ None ] + T
na_vrchu = 1

# spravíme si prázdne kôpky
kopky = [ [] for _ in range(M+Q+1) ]

# rozmiestnime tričká na kôpky podľa počtu nosení
for n in reversed(range(1,N+1)):
    kopky[ T[n] ].append(n)

odkial_ber = 0

# čítame otázky a simulujeme
for q in range(Q):
    if input() == 'Z':
        print(na_vrchu)
        kde = T[na_vrchu]
        kopky[kde].pop()
        kopky[kde+1].append(na_vrchu)
        T[na_vrchu] += 1
    else:
        while kopky[odkial_ber] == []:
            odkial_ber += 1
        nosil = kopky[odkial_ber].pop()
        print(nosil)
        na_vrchu = nosil
        kopky[odkial_ber+1].append(nosil)
        T[nosil] += 1

Iné efektívne riešenie môžeme založiť na použití pokročilejšej dátovej štruktúry: usporiadanej množiny. Presnejšie, dvoch takýchto množín. V jednej si budeme udržiavať všetky tričká usporiadané podľa toho, kedy boli naposledy nosené (čiže podľa poradia vo veľkej kope zhora dole) a v druhej budú usporiadané primárne podľa počtu nosení a až sekundárne podľa poradia vo veľkej kope.

Podľa toho, kto si v ten deň vyberá, vyberieme záznam o tričku zo začiatku jednej alebo druhej usporiadanej množiny. Následne tento záznam z oboch zmažeme a namiesto neho tam vložíme nový záznam, v ktorom už má toto tričko o jedno nosenie viac a navyše dostalo nový vyšší timestamp (čiže je aj naposledy nosené zo všetkých).

Každá operácia s usporiadanou množinou, v ktorej je \(n\) tričiek, nám trvá \(O(\log n)\), preto má toto riešenie časovú zložitosť \(O((n+q)\log n)\).

#include <bits/stdc++.h>
using namespace std;

struct tricko { int cislo, timestamp, pocet_noseni; };

struct porovnaj_timestamp {
    bool operator() (const tricko &A, const tricko &B) const { return A.timestamp > B.timestamp; }
};

struct porovnaj_pocet {
    bool operator() (const tricko &A, const tricko &B) const { 
        if (A.pocet_noseni != B.pocet_noseni) return A.pocet_noseni < B.pocet_noseni;
        return A.timestamp > B.timestamp; 
    }
};

int main() {
    int N, Q;
    cin >> N >> Q;

    // spravime si dve mnoziny triciek: jednu usporiadanu primarne podla poctu noseni,
    // druhu podla toho kedy bolo naposledy nosene
    set<tricko,porovnaj_pocet> najmenej_nosene;
    set<tricko,porovnaj_timestamp> naposledy_nosene;

    // ulozime tricka do oboch mnozin
    for (int n=0; n<N; ++n) {
        int t;
        cin >> t;
        najmenej_nosene.insert( {n+1, N-1-n, t} );
        naposledy_nosene.insert( {n+1, N-1-n, t} );
    }

    // spracuvame jednotlive dni
    for (int q=0; q<Q; ++q) {
        string kto;
        cin >> kto;
        tricko dnes;
        if (kto == "Z") dnes = *naposledy_nosene.begin(); else dnes = *najmenej_nosene.begin();
        cout << dnes.cislo << endl;
        najmenej_nosene.erase(dnes);
        naposledy_nosene.erase(dnes);
        dnes.timestamp = N+q; 
        ++dnes.pocet_noseni;
        najmenej_nosene.insert(dnes);
        naposledy_nosene.insert(dnes);
    }
}

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