Zadanie

Zlé jazyky hovoria, že programátori sa neumývajú. Celé dni a noci vraj nerobia nič iné, iba sa aktívne vyhýbajú sprche. To ale vôbec nie je pravda! Kde sa nabrali také hrozné fámy? Programátori sú predsa čistotní! Vedci z Katedry Sprchovania a Plávania sa teda rozhodli vyšetriť, ako to naozaj je.

V sprche používanej \(n\) programátormi je kopa sprchových gélov poukladaných jeden na druhom. Vždy, keď sa niekto sprchuje, vyberie svoj sprchový gél z kopy, čím sa všetky gély, ktoré boli nad ním, posunú nižšie. No a keď sa dosprchuje, položí svoj gél na samý vrch kopy. Každý programátor sa pritom sprchuje najviac raz denne (inak by sa rozpustil, však áno) a v kope má práve jeden vlastný sprchový gél, ktorý je označený tak, aby si ho nepomýlil.

Vedci si zaznamenali, ako vyzerala kopa gélov ráno a ako vyzerala večer, po tom ako sa všetci programátori (ktorí chceli) dosprchovali. Z týchto údajov chcú zistiť, koľko najviac a koľko najmenej programátorov sa počas dňa mohlo osprchovať.

Úloha

Na vstupe dostanete dva popisy kopy so sprchovými gélmi, jeden z rána a jeden z večera.

Každý sprchový gél je označený jedným číslom od \(1\) po \(n\). Čísla sa vrámci jedného popisu neopakujú. Popisy ranného a večerného zásobníka budú teda dve permutácie čísiel od \(1\) po \(n\). Zistite, koľko najmenej a koľko najviac programátorov sa mohlo počas dňa osprchovať, aby to zodpovedalo danému stavu zásobníka.

Formát vstupu

Prvý riadok vstupu obsahuje prirodzené číslo \(n\), udávajúce počet programátorov a teda aj počet sprchových gélov v kope.

Ďalšie dva riadky obsahujú popis kopy ráno a večer – permutáciu \(n\) čísiel od \(1\) po \(n\) oddelených medzerami. Čísla sú napísané v poradí od spodku kopy po vrch.

Číslo sady 1 2 3 4 5 6
Počet gélov (\(n\)) \(5\) \(50\) \(500\) \(5\,000\) \(50\,000\) \(500\,000\)

Formát výstupu

Vypíšte dva riadky, každý obsahujúci jedno celé číslo. V prvom riadku bude najmenší počet programátorov, ktorí sa mohli v ten deň osprchovať, v druhom najväčší možný počet.

Príklad

Input:

5
1 5 3 2 4
1 3 4 5 2

Output:

2
5

Presunutím jedného čísla z prvej permutácie na jej koniec sa nám nikdy nepodarí vytvoriť druhú permutáciu. Sprchovať sa preto museli aspoň dvaja programátori a to najskôr programátor s gélom číslo 5 a potom s gélom číslo 2.

Poďme si princíp vysvetliť na príkade. Majme 7 sprchových gélov, ktoré boli na začiatku na kope v stave 0, 1, 2, 3, 4, 5, 6 a po jednom dni sprchovania v stave 0, 1, 3, 4, 6, 5, 2 (v týchto príkladoch za “spodok” kopy považujeme ľavú stranu riadku).

Najmenší možný počet

Keď sa programátor sprchuje, tak vytiahne svoj sprchový gél z ľubovoľnej pozície v kope a položí ho na vrch kopy. To nič nemení na kope pod ním ani nad ním, okrem najvyššej pozície. Preto, ak sa spodky počiatočnej aj výslednej kopy zhodujú, znamená to, že tieto gély neboli použité – v našom prípade gély 0, 1. Použitý gél sa prejaví tak, že chýba vo výslednej postupnosti na svojom očakávanom mieste – gél 2 v druhej postupnosti chýba. Gély nad ním (ak nie sú použité) sú ale stále v nezmenenom poradí – gély 3, 4. Ďalej je pôvodné poradie opäť narušené, lebo bol použitý gél 5.

Vo výslednej postupnosti na pôvodných miestach teda chýbajú gély 2, 5, a preto je v tomto príklade odpoveďou \(2\).

Najväčší možný počet

Tu je odpoveď celkom zrejmá. Každý programátor sa sprchuje najviac raz za deň. Nech výsledná kopa vyzerá akokoľvek, vždy ju vieme vytvoriť tak, že sa osprchujú všetci programátori práve v poradí, v akom sú gély vo výslednej kope. Teda, ak sa chce sprchovať čo najväčší počet programátorov, každý sa bude sprchovať práve raz. Odpoveď je teda \(n\).

Poďme implementovať

Základná myšlienka algoritmu je, že máme 2 ukazovatele, jeden do každého z dvoch polí. Najskôr ukazujú na počiatočnú pozíciu. Máme tiež premennú, kde si pamätáme, koľko použitých šampónov sme našli.

Ak sa čísla šampónov, na ktoré ukazovatele ukazujú, zhodujú, oba sa posunú o jednu pozíciu doprava. Našli sme nepoužitý gél.

Ak sa niekde nezhodujú,1 zvýšime počet osprchovaných programátorov a preskočíme použitý gél v pôvodnej postupnosti (posunieme ukazovateľ o jedno doprava). Postupnosti sa budú zhodovať, až kým nenájdeme ďalší použitý gél.

Postup opakujeme, kým neprejdeme celú pôvodnú postupnosť. Na konci budeme mať najmenší možný počet osprchovaných programátorov.

Zložitosti

Z popisu algoritmu je zrejmé, že časová zložitosť bude \(O(n)\), lebo každú postupnosť prejdeme nanajvýš raz. Lepšia časová zložitosť sa dosiahnuť nedá, lebo musíme načítať celý vstup. Pamäťová zložitosť bude tiež \(O(n)\). Lepšie to opäť nejde, lebo keď postupnosti prechádzame, musíme si aspoň jednu pamätať celú.

#include<cstdio>

#define For(i, n) for(int i = 0; i < n; i++) 

int n;
int povodna[500042], vysledna[500042];

int main() {
    scanf(" %d", &n);
    For(i, n) scanf(" %d", &povodna[i]);
    For(i, n) scanf(" %d", &vysledna[i]);

    int a = 0, b = 0, pouzite = 0;
    
    while(a < n){
        if(povodna[a] == vysledna[b]) {
            a++;
            b++;
        } else {
            a++;
            pouzite++;
        }
    }

    printf("%d\n%d\n", pouzite, n);
    return 0;
}
input()                # n nas nezaujima :P
povodna_kopa = input().split()
vysledna_kopa = input().split()

b = 0
vysledok = 0

for gel in povodna_kopa:
    if gel == vysledna_kopa[b]:
        b += 1         # Kopy sa zhoduju, ideme dalej
    else:
        vysledok += 1  # Niekto sa osprchoval

print('{0}\n{1}'.format(vysledok, len(povodna_kopa)))

  1. Tak hurá! Niekto prekonal svoju averziu k vode a osprchoval sa!

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