Zadanie

Prichádza zima. Medvede sa dávno uložili na zimný spánok, lastovičky a dážďovníky odleteli, študenti dopísali zápočtové testy a do skúškového budú tiež už len spať. Príroda sa pomaly, pomaličky, veľmi pomaly zastavila.

Ale práca na novej sérii KSP sa nezastavuje nikdy. A keďže všetci starí vedúci a vedúce by radi oslavovali číru, nádhernú, dlhosiahlu existenciu KSP, treba zaučiť nových vedúcich, aby stimulovali (alebo aspoň simulovali) pracovnú morálku. Noví vedúci sa musia naučiť ešte veľa, aby mohli o sebe hrdo prehlásiť, že vedúcujú KSP. Našťastie, KSP ponúka bezchybný spôsob na určenie, či je niekto naozaj nový vedúci alebo sa tak len tvári.

Úloha

Každý nový vedúci sa po príchode do KSP postupne naučí \(n\) pre neho dôležitých informácí o fungovaní KSP. Tieto informácie si môžeme predstaviť, ako čísla od \(1\) po \(n\). Informácie sa naučí presne v poradí od \(1\) po \(n\). Mozog nového vedúceho ale funguje prazvláštne: informácie sú v ňom uložené lineárne, zľava doprava. A vždy, keď sa nový vedúci naučí nejakú novú informáciu, jeho mozog ju spracuje práve jednou z troch možností:

  • uloží si ju doľava (ak boli v mozgu informácie 1 2 3, budú tam 4 1 2 3)
  • uloží si ju doprava (ak boli v mozgu informácie 1 2 3, budú tam 1 2 3 4)
  • instantne ju zabudne (ak boli v mozgu informácie 1 2 3, budú tam, ako inak, 1 2 3)

Keď takto nový vedúci spracuje všetky informácie, dokončí svoju prvú úlohu do KSP a následne zabudne aj tie informácie, ktoré si ešte pamätá. Informácie zabúda v poradí, v akom ich má uložené v mozgu – postupne zľava doprava.

Práve sme vypočuli \(t\) ľudí, ktorí o sebe tvrdia, že sú novými vedúcimi KSP a všetkých sme sa pýtali, v akom poradí získané informácie zabúdali. Pre každého z nich chceme určiť, či daný človek môže byť novým vedúcim.

Formát vstupu

Na prvom riadku sa nachádza číslo \(t\), počet ľudí. Nasleduje \(t\) dvojíc riadkov, kde na prvom riadku dvojice je číslo \(n\), počet informácií. Na druhom riadku je permutácia prvých \(n\) prirodzených čísel - poradie, v akom daný človek informácie zabúdal.

Formát výstupu

Pre každého z \(t\) ľudí vypíšte jeden riadok s textom Novy veduci, ak mohol daný človek byť novým vedúcim, alebo s textom Neveduci, ak nemohol.

Obmedzenia

Sú \(4\) sady vstupov po \(2\) body. Platia v nich nasledovné obmedzenia:

Sada \(1\) \(2\) \(3\) \(4\)
\(1 \leq n \leq\) \(10\) \(100\) \(1\,000\) \(100\,000\)
\(1 \leq t \leq\) \(1\) \(10\) \(100\) \(1000\)
\(1 \leq \sum_t n \leq\) \(10\) \(100\) \(1\,000\) \(100\,000\)

Príklad

Input:

3
6
1 2 3 4 5 6
5
2 4 1 5 3
6
2 4 6 5 3 1

Output:

Novy veduci
Neveduci
Novy veduci

Prvý človek mohol napríklad všetky informácie instantne zabudnúť alebo prvé tri zabudnúť a zvyšné 3 si zapamätať sprava.

Druhá osoba určite nie je skutočná vedúca, poradie si musela vymyslieť.

Tretí človek si mohol prvú informáciu zapamätať sprava, druhú a štvrtú zabudnúť a ostatné zapamätať zľava. Jeho mozog by v tomto prípade vyzeral po získaní všetkých informácii takto: 6 5 3 1.

Pomalé riešenie

Každá informácia mala práve tri možnosti, čo sa s ňou mohlo stať (byť zabudnutá, zapamätaná zľava, zapamätaná sprava). Túto znalosť môžeme využiť na to, aby sme vygenerovali (napríklad rekurzívne) všetky možné postupnosti patriace novým vedúcim. Potom všetky prejdeme a zistíme, či sa nejaká zhoduje so vstupnou. Dokonca si ich ani nemusíme pamätať, stačí každú postupnosť porovnať rovno potom, čo ju vytvoríme. Tento prístup určite funguje, ale jeho časová zložitosť je bolestivá: potrebujeme vygenerovať \(3^n\) postupností dĺžky \(n\) a každú porovnať so vstupnou. Takéto riešenie teda nebude fungovať pre \(n\) rádovo väčšie, než napríklad 10.

Vzorové riešenie

Alebo sa najskôr zamyslime nad tým, ako by mohla postupnosť zabúdaných informácií vyzerať v nejakom všeobecnom prípade. Ak je náš človek naozaj nový vedúci, potom niekoľko informácií zabudol instantne (\(I\)), niekoľko si zapamätal zľava (\(L\)), a niekoľko sprava (\(P\)), pričom niekoľko môže byť aj 0. Vieme si to predstaviť aj tak, že existujú tri nezávislé priehradky, do ktorých informácie postupne ukladal, a na konci ich jednoducho prilepil za seba, v poradí \(I\), prevrátené \(L\) (pretože informácie z \(L\) vyberáme v opačnom poradí, ako sme ich tam) dávali, a \(R\).

Každá priehradka má prvky v stúpajúcom poradí - keďže informácie v stúpajúcom poradí prichádzali, nemôže to ani byť inak. Takže keď boli prilepené za seba, vznikla postupnosť čísel, ktorá najskôr niekoľkokrát stúpala (\(I\)), potom klesala (prevrátené \(L\)) a nakoniec znova stúpala (\(R\)). Medzi stúpajúcou a klesajúcou postupnosťou je buď nárast alebo pokles, čo vieme interpretovať ako súčasť ľubovoľnej z nich.

Pre každú zadanú postupnosť nám teda stačí overiť, či má takýto formát. Na to potrebujeme zistiť počet zmien jej smeru. Postupnosť budeme prechádzať postupne, a každý prvok porovnáme s predošlým. Začneme so stúpajúcim smerom postupnosti, (prvá priehradka je \(I\)) a vždy, keď sa smer zmení, prirátame si k počtu zmien 1. Nakoniec overíme, či je počet zmien menší alebo rovný dvom - to zodpovedá prechodom medzi \(I\) a \(L\) a medzi \(L\) a \(R\). Ak nastalo viac zmien, určite nešlo o nového vedúceho.

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

Každú postupnosť prejdeme práve raz, a pre každý jej prvok vykonáme konštantný počet operácií, takže časová zložitosť pre jedného človeka je \(O(n)\). Pre \(t\) ľudí potom \(O(\sum_t n)\). Pamäťová zložitosť je dokonca konštantná, pretože nám stačí pamätať si počet zmien a aktuálny smer postupnosti.


def clovek():
    n = int(input())
    post = list(map(int, input().split()))

    if n < 4:
        return True

    zmen = 0
    stup = True
    for i in range(1, n):
        akt = post[i] > post[i - 1]
        if akt != stup:
            stup = not stup
            zmen += 1
            if zmen > 2:
                return False
    return True

for i in range(int(input())):
    print("Novy veduci" if clovek() else "Neveduci")
#include <iostream>

using namespace::std;

int main(){
    int t, n, x, lastx, zmen;
    bool stup;

    cin >> t;
    while (t--){
        stup = true;
        zmen = 0;
        cin >> n;
        cin >> lastx;
        while (--n){
            cin >> x;
            if (stup != (x > lastx)){
                stup = !stup;
                zmen++;
                if (zmen == 3){
                    cout << "Neveduci" << endl;
                    zmen++;
                }
            }
            lastx = x;
        }
        if (zmen <= 2) cout << "Novy veduci" << endl;
    }
}

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