2749 – Tată
De la Universitas MediaWiki
Cerința
Se dă un vector t=(t[1], t[2], ..., t[n])
care memorează numere naturale cuprinse între 0
și n
. Să se verifice dacă t
este sau nu vector de tați asociat unui arbore cu rădăcină.
Date de intrare
Programul citește de la tastatură numărul n
, iar apoi n
numere naturale, separate prin spații.
Date de ieșire
Programul va afișa pe ecran mesajul DA
, dacă t
este vector de tați, sau mesajul NU
în caz contrar.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".
Restricții și precizări
1 ≤ n ≤ 100.000
0 ≤ t[i] ≤ n
Exemplul 1:
Intrare
5 0 1 1 3 3
Ieșire
DA
Exemplul 2:
Intrare
5 2 0 2 5 4
Ieșire
NU
Explicație
Nodul 4
are ca tată pe 5
, iar nodul 5
are ca tată pe 4
Exemplul 3:
Intrare
100001
Consola
Datele nu corespund restrictiilor impuse
Rezolvare
def sunt_restrictii_incorecte(n, t):
# Verifică restricțiile pentru n
if not (1 <= n <= 100000):
return True
# Verifică restricțiile pentru t[i]
for i in range(n):
if not (0 <= t[i] <= n):
return True
return False
def este_vector_de_tati(t):
n = len(t)
# Verifică dacă restricțiile sunt respectate
if sunt_restrictii_incorecte(n, t):
return False
# Verifică dacă rădăcina arborelui este corectă
if t[0] != 0:
return False
# Verifică dacă fiecare element al vectorului este un index valid
for i in range(1, n):
if not (0 <= t[i] < n):
return False
return True
# Citeste numarul n
n = int(input("Introduceti numarul n: "))
# Ieși din program dacă restricțiile pentru n nu sunt respectate
if n < 1 or n > 100000:
print("Datele nu corespund restrictiilor impuse")
else:
# Citeste vectorul t
t = list(map(int, input("Introduceti vectorul t: ").split()))
# Verifica daca restrictiile sunt respectate si afiseaza mesajul corespunzator
if sunt_restrictii_incorecte(n, t):
print("Datele nu corespund restrictiilor impuse")
else:
# Verifica daca t este vector de tati si afiseaza rezultatul
if este_vector_de_tati(t):
print("DA")
else:
print("NU")