Koniec kola: 5. august 2019 23:59
20 days
Počet bodov:
Program:  15b

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 Romanovi na roman.sobkuliak@trojsten.sk

V Absurdistane už od nepamäti funguje inštitúcia OIA (Ochrana Integrity Absurdistanu). V poslednej dobe sa ale na ňu valí veľká vlna kritiky. Špión Paroháč pri poslednej misii v Blahostane špiónoval tak dobre, že sa mu podarilo preniknúť do radov miestnej inštitúcie OIB (Ochrana Integrity Blahostanu). Tí mu ponúkli lukratívne miesto, ktorému Paroháč neodolal a prezliekol kabát. Pre Absurdistan teraz Paroháč predstavuje hrozbu.

Zatiaľ o Paroháčovom prešľape vie iba Hlaváč, šéf OIA. Na zatknutí Paroháča už aktívne pracuje. Zatiaľ vytvoril sieť zo svojich špiónov, v ktorej každý špión sleduje práve jedného iného špióna. Navyše, pretože Hlaváč neverí nikomu, platí, že každý špión je sledovaný práve jedným iným špiónom.

Hlaváč plánuje vyslať všetkých špiónov do Blahostanu. Potrebuje z nich vybrať čo najviac takých, ktorým o Paroháčovom prešľape povie. Nemôže však vybrať všetkých – aby dokonale fungovala jeho stratégia vzájomnej kontroly, musí každý zo špiónov, ktorý o prešľape vie, byť sledovaný špiónom, ktorý o prešľape nevie. Hlaváčovi by teraz veľmi pomohlo, keby ste zistili, koľko takýchto špiónov môže vybrať.

Úloha

Na vstupe dostane sieť špiónov, o ktorej platí, že každý špión sleduje práve jedného iného špióna a práve jedným špiónom je aj on sám sledovaný. Vašou úlohou je nájsť maximálny počet špiónov, ktorým môže Hlaváč vyzdradiť tajomstvo o Paroháčovi tak, aby platilo, že každý z týchto špiónov je sledovaný špiónom, ktorý o tajomstve nevie.

Formát vstupu

Na prvom riadku vstupu je jedno kladné číslo \(n\) (\(2 \leq n \leq 10^{6}\)), počet špiónov. Tých si očíslujeme od 1 po \(n\). Na druhom riadku vstupu je \(n\) medzerou oddelených čísel, pričom \(i\)-te číslo je číslo špióna, ktorý je sledovaný \(i\)-tym špiónom.

Formát výstupu

Na výstup vypíšte jediné číslo – maximálny počet špiónov, ktorým vie Hlaváč vyzdradiť svoje tajomstvo.

Hodnotenie

Číslo sady 1 2 3 4 5
maximálne \(n\) \(10\) \(20\) \(1000\) \(200\,000\) \(1\,000\,000\)

Príklady

Input:

5
5 3 2 1 4

Output:

2

Hlaváč môže svoje tajomstvo povedať napríklad špiónom 3 a 4. Špión 3 je sledovaný špiónom 2 a špión 4 špionom 5, pričom 2 ani 5 o tajomstve nevedia. Uvedomte si, že viac špiónov vybrať nemôžeme, pretože inak by nutne aspoň jeden z nich bol sledovaný iným z vybraných špiónov. Odpoveď je preto 2.

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.