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ú tam4 1 2 3
) - uloží si ju doprava (ak boli v mozgu informácie
1 2 3
, budú tam1 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.
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.