Un arbore binar
se numeste strict daca toate nodurile sale interne au exact doi fii.
Se da un set de n arbori binari
stricti fiecare avand m noduri
numerotate de la 1 la m.
Definim recurent egalitatea dintre doi arbori avand radacinile fixate in nodurile
x, respectiv y.
A(x) = A(y) daca:
x,y nu au fii
sau
x,y au fii, A(fiu_drept(x))
= A(fiu_drept(y)) si A(fiu_stang(x))
= A(fiu_stang(y))
(unde am notat cu A(x) arborele
cu radacina in x)
La fel putem defini relatia de ordine "<" intre doi arbori A(x) si A(y).
A(x) < A(y) daca:
x nu are fii si y
are fii
sau
nodurile x si y au fii iar A(fiu_stang(x)) < A(fiu_stang(y))
sau
nodurile x si y au fii, A(fiu_stang(x)) = A(fiu_stang(y)) si A(fiu_drept(x)) < A(fiu_drept(y))
Cerinta
Sa se determine lungimea celui mai lung subsir (nu neaparat strict) "crescator"
de arbori din setul dat conform cu relatia de ordine definita mai sus.
Date de intrare
Fisierul de intrare strict.in are urmatoarea structura:
- pe prima linie sunt scrise doua numere naturale separate prin spatiu n
m, reprezentând numarul de arbori si respectiv dimensiunea arborilor
- pe fiecare dintre urmatoarele n linii se gasesc cate m - 1 + (m + 1)
/ 2 numere; pe linia i + 1 se gasesc informatiile necesare pentru arborele i astfel: pentru fiecare nod de la 1
la m este scris 0
daca nodul nu are fii sau sunt scrise doua numere reprezentand fiul stang si
respectiv, fiul drept; mai intai este descris nodul 1, apoi nodul 2 etc. Linia:
0 0 5 1 0 0 7 3 2 4 inseamna
ca nodurile 1 si 2 nu au fii, nodul 3 il are ca fiu stang pe nodul 5 si ca fiu
drept pe nodul 1, nodul 4 nu are fii s.a.m.d.
Date de iesire
Fisierul de iesire strict.out va contine un singur numar reprezentand lungimea celui mai lung subsir crescator.
Restrictii
0 < n <= 10000
0 < m <= 51 Campionii isi pot da
seama de ce intr-un arbore binar strict exista un singur nod care poate indeplini
rolul de radacina a arborelui. Din aceasta cauza relatia de ordine e bine definita.
40% din teste vor avea n <=
5000 si m <= 31.
Participantii sunt incurajati sa foloseasca pentru citirea datelor functii ca
fgets() sau fread()!
Fie x=(x1, x2,
..., xn) un sir de n
elemente. Un subsir al lui x este format din elemente din x,
in ordinea in care acestea apar in x (xi1, xi2,
..., xik cu i1<i2<...<ik).