nivele

Nivele

== include(page="template/taskheader" task_id="nivele") ==

Poveste si cerinta...

Un arbore binar se numeste strict daca toate nodurile sale interne au exact doi fii. Definim nivelul unui nod din arbore, recursiv, astfel:
 
* Nivelul nodului radacina este $1$
* Nivelul oricarui nod diferit de nodul radacina este nivelul tatalui sau $+1$
 
Vom numi _sir de nivele_ orice secventa de numere care poate reprezenta nivelele frunzelor unui arbore binar strict, cand este parcurs in 'preordine':http://www.nist.gov/dads/HTML/preorderTraversal.html. Dandu-se $T$ secvente de numere sa se determine pentru fiecare daca sunt siruri de nivele.

h2. Date de intrare

Fisierul de intrare $nivele.in$ ...

Fisierul de intrare $nivele.in$ contine pe prima linie numarul $T$. Urmatoarele $T$ linii contin cate o secventa de numere: $N A{~1~} A{~1~} ... A{~N~}$.
 

h2. Date de iesire

In fisierul de iesire $nivele.out$ ...

In fisierul de iesire $nivele.out$ se vor scrie $T$ linii, cate una pentru fiecare secventa din fisierul de intrare. Daca o secventa de numere este un sir de nivele se va scrie $DA$, altfel se va scrie $NU$.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ T ≤ 10$
* $1 ≤ N ≤ 50.000$
* $1 ≤ A{~i~} ≤ 10^9^$

h2. Exemplu
table(example). |_. nivele.in |_. nivele.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 2
3 2 3 3
3 2 3 4
| DA
NU |

h3. Explicatie

...

Pentru primul exemplu putem construi urmatorul arbore binar strict:
!problema/nivele?arbore.jpg!

== include(page="template/taskfooter" task_id="nivele") ==

2719