0673 - Dif Sub
Cerința
Considerăm un arbore binar cu n
noduri în care fiecare nod este numerotat de la 1
la n
ș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 difsubIN.txt
conține pe prima linie numărul n
. Fiecare dintre următoarele n
linii contine câte 3
numere X st dr
; linia i + 1
din fișier conține informatiile despre nodul numerotat cu i
: X
reprezintă valoare din nod, st
reprezintă numărul de ordine al descendentului stâng sau 0
dacă nodul i
nu are descendent stâng, iar dr
reprezintă numărul de ordine al descendentului drept sau 0
dacă nodul i
nu are descendent drept.
Date de ieșire
Fișierul de ieșire difsubOUT.txt
va conține pe prima linie numărul D
, 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
1 ≤ n ≤ 1000
- valorile din nodurile arborelui vor fi mai mici sau egale cu
1.000.000
Exemplul 1:
difsubIN.txt
6 2 3 5 6 0 6 1 0 0 7 1 2 4 0 0 10 0 0
difsubOUT.txt
9
Exemplul 2:
difsubIN.txt
1001 2 3 5 6 0 6 1 0 0 7 1 2 4 0 0 10 0 0
difsubOUT.txt
Datele nu corespund restrictiilor impuse
Rezolvare
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()