Telefonul

Time limit: 3s Memory limit: 64MB Input: Output:

ASG și-a luat un telefon nou de la magazinul din colțul străzii. Era un Nokia vechi cu butoane. L-a desfăcut și l-a pus lângă birou și a mers să se joace Fortnite cu niște prieteni, însă și-a luat bătaie atât de tare încât, de nervi, a spart telefonul de masă. Astfel, pe telefonul lui se pot vedea acum doar steluțe. ASG, fiind băiat deștept, a observat o regula de creare. Telefonul a generat un anume număr de linii, iar numerele de stele de pe fiecare linie sunt, de la prima la ultima, numere Fibonacci consecutive.

Cerință

Dânduse un astfel de desen, să se determine dacă ar putea apărea sau nu pe telefonul lui ASG.

Date de intrare

Pe prima linie se găsește un singur număr natural NN, numărul de linii al desenului.
Pe următoarele NN linii se vor găsi un anumit număr de steluțe *.

Date de ieșire

Dacă steluțele pot fi afișate pe telefonul lui ASG se va afișa DA, altfel NU.

Restricții și precizări

  • 1N391 \leq N \leq 39;
  • 11 \leq numărul de steluțe de pe fiecare linie 63 245 986\leq 63 \ 245 \ 986.
  • Un număr Fibonacci este suma celor doua numere de dinaintea lui. F0=0F_0 = 0, F1=1F_1 = 1, F2=1F_2 = 1, iar de aici, Fi=Fi1+Fi2F_{i} = F_{i - 1} + F_{i - 2}.
  • Este garantat că, în afară de prima linie pe care se găsește numărul natural NN, se vor afla doar steluțe pe toate celelalte linii.

Exemplul 1

stdin

3
*
*
**

stdout

DA

Explicație

11, 11 și 22 sunt, în ordine, numărul de steluțe de pe fiecare linie, iar acestea sunt numerele fibonacci de pe pozițiile 11, 22 și 33.

Exemplul 2

stdin

2
****
******

stdout

NU

Explicație

Avem numerele 44 și 66. Acestea nu sunt numere Fibonacci consecutive (nici măcar nu sunt Fibonacci), așa că răspunsul este NU.

Log in or sign up to be able to send submissions!