4156 – Nivele Pare
Enunț
Într-un arbore cu rădăcină, nivelul unui nod este lungimea lanțului de la rădăcină la acel nod. Astfel, rădăcina este pe nivelul 0
, fiii rădăcinii pe nivelul 1
, fiii fiilor rădăcinii pe nivelul 2
, etc.
Cerința
Se dă vectorul de tați al unui arbore cu rădăcină cu n
noduri. Determinați nodurile situate pe nivele pare.
Date de intrare
Fișierul de intrare nivelepareIN.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
Fișierul de ieșire nivelepareOUT.txt
va conține mai multe linii. Fiecare linie i
conține, în ordine crescătoare, nodurile aflate pe nivelul 2*(i-1)
.
Restricții și precizări
1 ≤ n ≤ 100
- în vectorul de tați rădăcina este marcată cu
0
Exemplul 1:
nivelepareIN.txt
8 4 3 0 3 2 1 2 1
nivelepareOUT.txt
3 1 5 7
Exemplul 2:
nivelepareIN.txt
101 4 3 0 3 2 1 2 1
nivelepareOUT.txt
Datele nu corespund restrictiilor impuse
Rezolvare
<syntaxhighlight lang="python3" line="1"> def verifica_restrictii(n):
if 1 <= n <= 100: return True return False
def citeste_arbore_din_fisier(file_path):
with open(file_path, 'r') as file: n = int(file.readline()) if not verifica_restrictii(n): return None, None, "Datele nu corespund restrictiilor impuse" parinti = list(map(int, file.readline().split())) return n, parinti, None
def scrie_noduri_pe_nivele_pare(file_path, nivele_pare):
with open(file_path, 'w') as file: for nivel in nivele_pare: file.write(' '.join(map(str, nivel)) + '\n')
def noduri_pe_nivele_pare(n, parinti):
nivele_pare = [[] for _ in range(n)]
for i in range(n): parinte = parinti[i] nivel = 0 while parinte != 0: nivel += 1 parinte = parinti[parinte - 1]
if nivel % 2 == 0: nivele_pare[nivel // 2].append(i + 1)
return nivele_pare
if __name__ == "__main__":
input_file = "nivelepareIN.txt" output_file = "nivelepareOUT.txt"
n, parinti, restrictii_msg = citeste_arbore_din_fisier(input_file)
if restrictii_msg: with open(output_file, 'w') as file: file.write(restrictii_msg) else: nivele_pare = noduri_pe_nivele_pare(n, parinti) scrie_noduri_pe_nivele_pare(output_file, nivele_pare)
</syntaxhighlight>