Fişierul intrare/ieşire:politic2.in, politic2.outSursăLot Focsani 2016, Baraj 3 Seniori
AutorRares BuhaiAdăugată dedepevladVlad Dumitru-Popescu depevlad
Timp execuţie pe test0.05 secLimită de memorie128000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Politic2

Există N candidaţi la alegerile prezidenţiale. Fiecare dintre cei N candidaţi ştie exact cu cine va vota. O persoană poate vota o singură altă persoană (se poate vota şi pe sine). Scopul tău este să creezi confuzie între candidaţi. Pentru asta, ai dreptul să le interzici unor cel mult K dintre candidaţi să participe. Atunci când un candidat este eliminat, toţi candidaţii care ar fi votat cu el votează cu persoana cu care ar fi votat candidatul eliminat (deoarece au încredere în decizia sa). Dacă cel eliminat ar fi votat cu sine sau era INDECIS, toţi cei care ar fi votat cu el devin INDECIŞI. Pe scurt, dacă A votează cu B şi B votează cu C, după ce îl elimini pe B, A va vota cu C. Dacă A votează cu B şi B votează cu B, după ce îl elimini pe B, A va deveni INDECIS. De asemenea, dacă A votează cu B şi B este INDECIS, după ce îl elimini pe B, A va deveni INDECIS. Un candidat este considerat DECIS dacă NU este eliminat şi NU este INDECIS.

Cerinta

Pentru fiecare K de la 1 la N, se cere numărul minim de candidaţi DECISI pe care îi putem avea dacă am elimina K candidaţi.

Date de intrare

Pe prima linie a fişierului de intrare politic2.in se va afla numărul natural N, reprezentând numărul de candidaţi. Urmează N linii. Pe linia i + 1 se va afla un număr natural, reprezentând candidatul cu care votează candidatul cu numărul i.

Date de iesire

Fişierul de ieşire politic2.out va conţine N linii. Pe linia i se va afişa un singur număr natural, reprezentând numărul minim de candidaţi DECISI în cazul în care eliminăm i candidaţi.

Restricţii

  • 1 ≤ N ≤ 1000
  • Pentru teste în valoare de 30 puncte, N ≤ 200
  • Candidaţii sunt indexaţi de la 1.

Exemplu

politic2.inpolitic2.outExplicatie
6
2
6
2
5
5
5
3
2
0
0
0
0
Eliminând candidatul 5, candidaţii 4 şi 6 devin indecişi, aşa ca rămân doar 3 candidaţi decişi (1, 2 şi 3).
Eliminând în continuare candidatul 6, candidatul 2 devine indecis fiindcă 6 era indecis.
Astfel, doar 1 şi 3 rămân decişi. Eliminând nodul 2, nu mai rămâne niciun candidat decis.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?