Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | nivele.in, nivele.out | Sursă | preONI 2008, Runda 4 |
| Autor | Mircea Bogdan Pasoi | Adăugată de |  Mircea Pasoi •domino |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 5120 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Nivele
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. Dandu-se T secvente de numere sa se determine pentru fiecare daca sunt siruri de nivele.
Date de intrare
Fisierul de intrare nivele.in contine pe prima linie numarul T. Urmatoarele T linii contin cate o secventa de numere: N A1 A1 ... AN.
Date de iesire
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.
Restrictii
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 50.000
- 1 ≤ Ai ≤ 109
Exemplu
| nivele.in | nivele.out |
|---|---|
| 2 3 2 3 3 3 2 3 4 | DA NU |
Explicatie
Pentru primul exemplu putem construi urmatorul arbore binar strict:
