Simina at 14:55, 27 December 2023

2023-12-27T14:55:14Z

← Older revision		Revision as of 14:55, 27 December 2023
Line 9:		Line 9:

	= Date de ieșire =		= Date de ieșire =
	Fișierul de ieșire <code>nivele11OUT.txt</code> va conține mai multe linii. Fiecare linie <code>i</code> conține, în ordine crescătoare, nodurile aflate pe nivelul <code>i-1</code>, separate prin câte un epațiu.		Fișierul de ieșire <code>nivele11OUT.txt</code> va conține mai multe linii. Fiecare linie <code>i</code> conține, în ordine crescătoare, nodurile aflate pe nivelul <code>i-1</code>, separate prin câte un epaț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 =		= Restricții și precizări =

Simina: Pagină nouă: == Enunț == Într-un arbore cu rădăcină, nivelul unui nod este lungime 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. Afișați parcurgerea pe nivele a arborelui dat. = Date de intrare = Fișierul de intrare `nivele11IN.txt`...

2023-12-26T22:36:20Z

Pagină nouă: == Enunț == Într-un arbore cu rădăcină, nivelul unui nod este lungime lanțului de la rădăcină la acel nod. Astfel, rădăcina este pe nivelul <code>0</code>, fiii rădăcinii pe nivelul <code>1</code>, fiii fiilor rădăcinii pe nivelul <code>2</code>, etc. = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri. Afișați parcurgerea pe nivele a arborelui dat. = Date de intrare = Fișierul de intrare <code>nivele11IN.txt</code>...

New page

== Enunț ==
Într-un arbore cu rădăcină, nivelul unui nod este lungime lanțului de la rădăcină la acel nod. Astfel, rădăcina este pe nivelul <code>0</code>, fiii rădăcinii pe nivelul <code>1</code>, fiii fiilor rădăcinii pe nivelul <code>2</code>, etc.

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri. Afișați parcurgerea pe nivele a arborelui dat.

= Date de intrare =
Fișierul de intrare <code>nivele11IN.txt</code> conține pe prima linie numărul de noduri <code>n</code>. 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 <code>nivele11OUT.txt</code> va conține mai multe linii. Fiecare linie <code>i</code> conține, în ordine crescătoare, nodurile aflate pe nivelul <code>i-1</code>, separate prin câte un epațiu.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* în vectorul de tați rădăcina este marcată cu <code>0</code>

= Exemplul 1: =
<code>nivele11IN.txt</code>
8
4 3 0 3 2 1 2 1
<code>nivele11OUT.txt</code>
3
2 4
1 5 7
6 8

= Explicație =
Pe nivelul 0 se află rădăcina, adică nodul 3. Pe nivelul 1 se află nodurile 2 și 4 (descentenții direcți ai rădăcinii). Pe nivelul 2 se află nodurile 1, 5 și 7. Pe ultimul nivel se află nodurile 6 și 8.

== Exemplul 2: ==
<code>nivele11IN.txt</code>
101
4 3 0 3 2 1 2 1
<code>nivele11OUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from collections import defaultdict, deque

def verificare_restrictii(n):
if 1 <= n <= 100:
return True
else:
with open('nivele11OUT.txt', 'w') as file:
file.write("Datele nu corespund restrictiilor impuse")
return False

def parcurgere_pe_nivele(n, tati):
if not verificare_restrictii(n):
return []

# Construim lista de adiacență pentru arbore
graf = defaultdict(list)
radacina = -1

for i in range(n):
parinte = tati[i]

if parinte == 0:
radacina = i + 1
else:
graf[parinte].append(i + 1)

# Folosim BFS pentru a parcurge nodurile pe nivele
nivele = []
vizitat = [False] * (n + 1)
queue = deque([(radacina, 0)]) # Rădăcina se află pe nivelul 0

while queue:
nod, nivel = queue.popleft()
if not vizitat[nod]:
vizitat[nod] = True

# Adăugăm nodul la lista corespunzătoare nivelului său
if len(nivele) <= nivel:
nivele.append([])
nivele[nivel].append(nod)

# Adăugăm fiii nodului în coadă cu nivelul actual + 1
for fiu in graf[nod]:
if not vizitat[fiu]:
queue.append((fiu, nivel + 1))

return nivele

# Citim datele din fișierul de intrare
with open('nivele11IN.txt', 'r') as file:
n = int(file.readline().strip())
tati = list(map(int, file.readline().strip().split()))

# Obținem rezultatul
rezultat = parcurgere_pe_nivele(n, tati)

# Dacă rezultatul nu este gol, scriem rezultatul în fișierul de ieșire
if rezultat:
with open('nivele11OUT.txt', 'w') as file:
for nivel in rezultat:
file.write(' '.join(map(str, nivel)) + '\n')

</syntaxhighlight>

4159 – Nivele11 - Revision history

Simina at 14:55, 27 December 2023