Fişierul intrare/ieşire:nivele.in, nivele.outSursăpreONI 2008, Runda 4
AutorMircea Bogdan PasoiAdăugată dedominoMircea Pasoi domino
Timp execuţie pe test0.1 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/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.innivele.out
2
3 2 3 3
3 2 3 4
DA
NU

Explicatie

Pentru primul exemplu putem construi urmatorul arbore binar strict:

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content