0640 – NrFii

From Bitnami MediaWiki

Cerința[edit]

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri. Determinați nodul din arbore cu număr maxim de fii. Dacă în arbore sunt mai multe noduri cu număr maxim de fii, afișați-le pe toate, în ordine crescătoare.

Date de intrare[edit]

Fișierul de intrare nrfiiIN.txt conține pe prima linie numărul de noduri n. Pe linia următoare se află vectorul de tați al arborelui, valorile fiind separate prin spații.

Date de ieșire[edit]

Fișierul de ieșire nrfiiOUT.txt va conține pe prima linie nodurile din arbore cu număr maxim de fii, în ordine crescătoare, separate printr-un spațiu.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

Restricții și precizări[edit]

  • 1 ≤ n ≤ 100
  • în vectorul de tați rădăcina este marcată cu 0

Exemplul 1:[edit]

nrfiiIN.txt

7
4 1 7 0 7 7 1 

nrfiiOUT.txt

7

Explicație[edit]

Nodul 7 are număr maxim de fii, 3.

Exemplul 2:[edit]

nrfiiIN.txt

101
4 1 7 0 7 7 1 

nrfiiOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare[edit]

<syntaxhighlight lang="python3" line="1"> def citeste_arbore(file_path):

   with open(file_path, 'r') as file:
       n = int(file.readline().strip())
       tati = list(map(int, file.readline().split()))
   return n, tati

def verificare_restrictii(n):

   if 1 <= n <= 100:
       return True
   else:
       with open("nrfiiOUT.txt", "w") as file_out:
           file_out.write("Datele nu corespund restrictiilor impuse")
       return False

def determina_noduri_max_fii(n, tati):

   fii = [0] * (n + 1)
   for tata in tati:
       if tata != -1:
           fii[tata] += 1
   max_fii = max(fii)
   noduri_max_fii = [i for i in range(1, n + 1) if fii[i] == max_fii]
   return noduri_max_fii

def scrie_rezultat(file_path, noduri_max_fii):

   with open(file_path, 'w') as file:
       if noduri_max_fii:
           file.write(' '.join(map(str, noduri_max_fii)))
       else:
           file.write("Datele nu corespund restrictiilor impuse")

if __name__ == "__main__":

   file_input = "nrfiiIN.txt"
   file_output = "nrfiiOUT.txt"
   n, tati = citeste_arbore(file_input)
   if verificare_restrictii(n):
       noduri_max_fii = determina_noduri_max_fii(n, tati)
       scrie_rezultat(file_output, noduri_max_fii)

</syntaxhighlight>