Editing 0673 - Dif Sub

= 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. Să se determine diferența în valoare absolută a sumei valorilor memorate în subarborele stâng al rădăcinii și suma valorilor memorate în subarborele drept al rădăcinii.

= Date de intrare =
Fișierul de intrare <code>difsubIN.txt</code> conține pe prima linie numărul <code>n</code>. Fiecare dintre următoarele <code>n</code> linii contine câte <code>3</code> numere <code>X st dr</code>; linia <code>i + 1</code> din fișier conține informatiile 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>difsubOUT.txt</code> va conține pe prima linie numărul <code>D</code>, cu semnificația precizată. Î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>difsubIN.txt</code>
 6
 2 3 5
 6 0 6
 1 0 0
 7 1 2
 4 0 0
 10 0 0
<code>difsubOUT.txt</code>
 9

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

== Rezolvare == 
<syntaxhighlight lang="python" line="1">
def check_restrictions(n, x):
    if not (1 <= n <= 1000):
        return False
    if not all(0 <= val <= 1000000 for val in x):
        return False
    return True

def SRD(k, st, dr, x):
    global d
    if st[k] != 0:
        SRD(st[k], st, dr, x)
    d += x[k]
    if dr[k] != 0:
        SRD(dr[k], st, dr, x)

def main():
    global d
    with open("difsubIN.txt", "r") as f:
        n = int(f.readline().strip())
        x = [0] * (n + 1)
        st = [0] * (n + 1)
        dr = [0] * (n + 1)
        nod = [0] * (n + 1)

        for i in range(1, n + 1):
            vals = f.readline().strip().split()
            if len(vals) != 3:
                with open("difsubOUT.txt", "w") as g:
                    g.write("Datele nu corespund restrictiilor impuse")
                return

            x[i] = int(vals[0])
            st[i] = int(vals[1])
            dr[i] = int(vals[2])
            if st[i]:
                nod[st[i]] = 1
            if dr[i]:
                nod[dr[i]] = 1

    if not check_restrictions(n, x[1:]):
        with open("difsubOUT.txt", "w") as g:
            g.write("Datele nu corespund restrictiilor impuse")
        return

    rad = 1
    while nod[rad]:
        rad += 1

    d = 0
    SRD(st[rad], st, dr, x)
    s = d
    d = 0
    SRD(dr[rad], st, dr, x)

    with open("difsubOUT.txt", "w") as g:
        if s > d:
            g.write(str(s - d))
        else:
            g.write(str(d - s))

if __name__ == "__main__":
    main()

</syntaxhighlight>