Editing 0677 - Nivele Bin

= Cerința =
Considerăm un arbore binar cu <code>n</code> noduri în care fiecare nod este numerotat de la <code>1</code> la <code>n</code> și conține o valoare număr natural. În acest arbore rădăcina este considerată pe nivelul <code>0</code>, descendenții direcți ai rădăcinii pe nivelul <code>1</code>, etc. Să se determine numărul de nivele <code>k</code> din arbore și, pentru fiecare nivel <code>i</code> de la <code>0</code> la <code>k</code>, numărul de noduri situate pe acel nivel.

= Date de intrare =
Fișierul de intrare <code>nivelebinIN.txt</code> conține pe prima linie numărul <code>n</code>. Fiecare dintre următoarele <code>n</code> linii conține câte <code>3</code> numere <code>X st dr</code>; linia <code>i + 1</code> din fișier conține informațiile despre nodul numerotat cu <code>i</code>: <code>X</code> reprezintă valoare din nod, <code>st</code> reprezintă numărul de ordine al descendentului stâng sau <code>0</code> dacă nodul <code>i</code> nu are descendent stâng, iar <code>dr</code> reprezintă numărul de ordine al descendentului drept sau <code>0</code> dacă nodul <code>i</code> nu are descendent drept.

= Date de ieșire =
Fișierul de ieșire <code>nivelebinOUT.txt</code> va conține pe prima linie numărul <code>k</code>, iar pe a doua linie <code>k+1</code> numere naturale separate prin exact un spațiu, al <code>i</code>-lea număr reprezentând numărul de noduri situate pe nivelul <code>i-1</code> din arbore. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n ≤ 1000</code>
* valorile din nodurile arborelui vor fi mai mici sau egale cu <code>1.000.000</code>

= Exemplul 1: =
<code>nivelebinIN.txt</code>
 6
 2 3 5
 6 0 6
 1 0 0
 7 1 2
 4 0 0
 10 0 0
<code>nivelebinOUT.txt</code>
 3
 1 2 3

= Explicație =
Exemplul corespunde arborelui de mai jos, în care au fost marcate cu albastru valorile din noduri, iar cu roșu numerele de ordine ale nodurilor.

Arborele conține trei nivele:

* nivelul <code>0</code> conține doar rădăcina, nodul numerotat cu <code>4</code>
* nivelul <code>1</code> conține două noduri, cele numerotate cu <code>1 2</code>
* nivelul <code>2</code> conține trei noduri, cele numerotate cu <code>3 5 6</code>

== Exemplul 2: ==
<code>nivelebinIN.txt</code>
 1001
 2 3 5
 6 0 6
 1 0 0
 7 1 2
 4 0 0
 10 0 0
<code>nivelebinOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def completniv(k, niv, nivele, s, d):
    if k != 0:
        nivele[k] = niv
        completniv(s[k], niv + 1, nivele, s, d)
        completniv(d[k], niv + 1, nivele, s, d)

def verifica_restrictii(n, noduri):
    if not (1 <= n <= 1000):
        return False
    for x, s, d in noduri:
        if x > 1000000 or s > 1000000 or d > 1000000:
            return False
    return True

def main():
    try:
        with open("nivelebinIN.txt", "r") as fin:
            n = int(fin.readline().strip())
            noduri = [tuple(map(int, fin.readline().strip().split())) for _ in range(n)]

            if not verifica_restrictii(n, noduri):
                raise ValueError("Datele nu corespund restrictiilor impuse")

            s = [0] * (n + 1)
            d = [0] * (n + 1)
            p = [0] * (n + 1)
            nivele = [0] * (n + 1)
            
            for i in range(1, n + 1):
                x, s[i], d[i] = noduri[i-1]
                p[s[i]] = 1
                p[d[i]] = 1

            r = 0
            for i in range(1, n + 1):
                if p[i] == 0:
                    r = i
                    break

            completniv(r, 0, nivele, s, d)
            
            nivmax = max(nivele)

            with open("nivelebinOUT.txt", "w") as fout:
                fout.write(f"{nivmax + 1}\n")
                for niv in range(nivmax + 1):
                    k = sum(1 for j in range(1, n + 1) if nivele[j] == niv)
                    fout.write(f"{k} ")

    except ValueError as e:
        with open("nivelebinOUT.txt", "w") as fout:
            fout.write(str(e))

if __name__ == "__main__":
    main()

</syntaxhighlight>