strict      

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).

    Exemplu

    strict.in strict.out Explicatie

    5 7
    0 0 5 1 0 0 7 3 2 4
    3 7 6 4 0 1 5 0 0 0
    7 5 0 0 0 6 3 0 2 4
    4 3 0 0 5 6 0 0 2 1
    2 5 3 4 0 7 6 0 0 0

    		 3

    O solutie poate fi reprezentata de arborii 2, 3 si 5

    Timp maxim de executie/test : 0.1 secunde

    Iolanda Popa
    studenta - Facultatea de Informatica, Iasi
    Contact: iolivp@gmail.com