Simina: Pagină nouă: == Enunț == Într-un arbore cu rădăcină, spunem că rădăcina este pe nivelul `1`, fiii rădăcinii pe nivelul `2`, fiii fiilor rădăcinii pe nivelul `3`, etc. = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu `n` noduri și `k` noduri din arbore. Determinați pentru fiecare dintre cele `k` noduri nivelul pe care se află. = Date de intrare = Fișierul de intrare `niveleIN.txt<...`


2023-12-26T21:34:36Z
Pagină nouă: == Enunț == Într-un arbore cu rădăcină, spunem că rădăcina este pe nivelul <code>1</code>, fiii rădăcinii pe nivelul <code>2</code>, fiii fiilor rădăcinii pe nivelul <code>3</code>, etc.  = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și <code>k</code> noduri din arbore. Determinați pentru fiecare dintre cele <code>k</code> noduri nivelul pe care se află.  = Date de intrare = Fișierul de intrare <code>niveleIN.txt<...
New page
== Enunț ==

Într-un arbore cu rădăcină, spunem că rădăcina este pe nivelul <code>1</code>, fiii rădăcinii pe nivelul <code>2</code>, fiii fiilor rădăcinii pe nivelul <code>3</code>, etc.



= Cerința =

Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și <code>k</code> noduri din arbore. Determinați pentru fiecare dintre cele <code>k</code> noduri nivelul pe care se află.



= Date de intrare =

Fișierul de intrare <code>niveleIN.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. Linia a treia conține numărul <code>k</code>, iar linia a patra <code>k</code> noduri, <code>x[1]</code>, <code>x[2]</code>, … , <code>x[k]</code>.



= Date de ieșire =

Fișierul de ieșire <code>niveleOUT.txt</code> va conține <code>k</code> linii. Linia <code>i</code> va conține nivelul pe care se află nodul <code>x[i]</code> în arborele dat



= Restricții și precizări =



* <code>1 ≤ k ≤ n ≤ 100</code>

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



= Exemplul 1: =

<code>niveleIN.txt</code>

 7

 4 1 7 0 7 7 1 

 4

 1 3 4 7

<code>niveleOUT.txt</code>

 2

 4

 1

 3 



= Exemplul 2: =

<code>niveleIN.txt</code>

 101

 4 1 7 0 7 7 1 

 4

 1 3 4 7

<code>niveleOUT.txt</code>

 Datele nu corespund restrictiilor impuse



== Rezolvare ==

<syntaxhighlight lang="python3" line="1">

def verifica_restrictii(n, k, tati):

    if not(1 <= k <= n <= 100) or tati.count(0) != 1:

        with open("niveleOUT.txt", "w") as f_out:

            f_out.write("Datele nu corespund restrictiilor impuse")

        return False

    return True



def determina_nivelul(n, tati, k, noduri):

    # Verificare pentru restricții

    if not verifica_restrictii(n, k, tati):

        return



    nivele = [0] * n  # nivelele pentru fiecare nod

    radacina = tati.index(0) + 1  # găsim poziția rădăcinii în vectorul de tați



    def dfs(nod, nivel):

        nivele[nod - 1] = nivel  # nodurile sunt numerotate de la 1, așa că indexăm cu nod-1

        for fiu in range(1, n + 1):

            if tati[fiu - 1] == nod:

                dfs(fiu, nivel + 1)



    dfs(radacina, 1)



    rezultate = [nivele[nod - 1] for nod in noduri]



    # Scrierea rezultatelor în fișierul de ieșire

    with open("niveleOUT.txt", "w") as f_out:

        for rezultat in rezultate:

            f_out.write(str(rezultat) + "\n")



# Citirea datelor de intrare

with open("niveleIN.txt", "r") as f:

    n = int(f.readline().strip())

    tati = list(map(int, f.readline().split()))

    k = int(f.readline().strip())

    noduri = list(map(int, f.readline().split()))



# Determinarea nivelului pentru fiecare nod dat

determina_nivelul(n, tati, k, noduri)



</syntaxhighlight>

0638 – Nivele - Revision history