2110 - Vot

În clasa lui Andrei sunt n elevi, codificaţi cu numerele 1, 2, …, n. Ei au fost rugaţi de către diriginta lor să propună un coleg de clasă care să devină liderul lor. Fiecare elev şi-a exprimat opţiunea scriind pe un bileţel codul său şi codul elevului ales de el pentru funcţia de şef de clasă. În acest fel diriginta a putut afla pe cine a votat fiecare elev. După studierea propunerilor venite din partea elevilor săi, diriginta lui Andrei a dorit să determine un grup cât mai numeros de elevi care s-au votat unii pe alţii. Cu alte cuvinte, pentru fiecare elev din grup să existe un membru al grupului care să-l fi votat. Dacă de exemplu, sunt 5 elevi şi elevul 1 îl votează pe 3, 2 îl votează pe 4, votul lui 3 merge spre 2, al lui 4, spre 2 iar 5 se votează pe sine, grupul determinat va fi format din elevii 2, 4 şi 5. Să observăm că şi elevii din grupurile {2, 4} şi {5} îşi exercită votul în cadrul grupului dar aceste grupuri nu sunt maximale.

Cerința

Scrieţi un program care, pe baza voturilor elevilor clasei, să determine un grup cu un număr maxim de elevi pentru care voturile primite de ei provin de la elevi aparţinând aceluiaşi grup.

Date de intrare

Pe prima linie a fişierului vot.in se găseşte un număr natural n, reprezentând numărul de elevi din clasa lui Andrei. Pe linia a doua se dau n numere naturale din mulţimea {1, 2, …, n}, separate prin câte un spaţiu, reprezentând voturile elevilor, astfel: numărul  de pe pozitia i indică pe cine a votat elevul i.

Date de ieșire

Pe prima linie din fişierul vot.out se găseşte un număr natural m reprezentând numărul de elevi din grupul determinat. Pe linia a doua se găsesc, în ordine crescătoare, cele m coduri ale elevilor din grup.

Restricții și precizări

• 1< n ≤ 1000

• Este posibil ca un elev să se voteze pe sine.

Exemplu:

vot.in

10
10 3 3 1 1 5 1 1 7 9

vot.out

5
1 3 7 9 10

Explicație

Se observă că 1 îl votează pe 10, 3 se votează pe el însuşi, votul lui 7 merge spre 1, al lui 9 – spre 7 iar 10 îl votează pe 9, deci toti elevii din acest grup primesc voturi din partea unor elevi ai grupului şi acesta este maximal cu proprietatea cerută.<syntaxhighlight lang="python3"> import numpy as np

def main():

   # Deschidem fisierul de intrare "vot.in" pentru citire si fisierul de iesire "vot.out" pentru scriere.
   fin = open("vot.in", "r")
   fout = open("vot.out", "w")

   # Initializam array-uri pentru stocarea datelor
   numar_a = np.zeros(1001, dtype=int)
   numar_b = np.zeros(1001, dtype=int)
   numar_c = np.zeros(1001, dtype=int)

   # Citim numarul 'n' din prima linie a fisierului de intrare.
   numar_n = int(fin.readline())

   # Citim o linie de numere intregi separate prin spatiu si le stocheaza in array-ul 'a'.
   line = fin.readline().split()
   for i in range(1, numar_n + 1):
       # Converteste valorile citite din fisier in intregi si le stocheaza in 'a'.
       numar_a[i] = int(line[i - 1])
       # Incrementam contor pentru fiecare valoare din 'a' in array-ul 'b'.
       numar_b[numar_a[i]] += 1

   # Initializam pointeri si array suplimentar pentru a retine anumite valori.
   numar_p, numar_u = 1, 0

   # Identificam valorile care nu apar in 'a'.
   for i in range(1, numar_n + 1):
       if numar_b[i] == 0:
           numar_u += 1
           numar_c[numar_u] = i

   # Eliminam anumitor elemente din 'a' bazat pe contorul din 'b'.
   while numar_p <= numar_u:
       j = numar_c[numar_p]
       if numar_a[j] > 0 and numar_b[j] == 0:
           numar_b[numar_a[j]] -= 1
           if numar_b[numar_a[j]] == 0:
               numar_u += 1
               numar_c[numar_u] = numar_a[j]
           numar_a[j] = 0
       numar_p += 1

   # Scriem rezultatul in fisierul de iesire
   fout.write(str(numar_n - numar_u) + "\n")
   for i in range(1, numar_n + 1):
       if numar_a[i] > 0:
           fout.write(str(i) + " ")

   # Inchidem fisierele de intrare si iesire.
   fin.close()
   fout.close()

if __name__ == "__main__":

   main()

</syntaxhighlight>