| Fişierul intrare/ieşire: | ciuperci.in, ciuperci.out | Sursă | .com 2011 |
| Autor | Radu Stefan Voroneanu | Adăugată de |  Mr. Noname •cezar305 |
| Timp execuţie pe test | 0.6 sec | Limită de memorie | 5120 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Ciuperci
Un arbore este super-echilibrat daca are urmatoarele proprietati:
● este binar, deci fiecare nod are maxim 2 fii.
● pentru fiecare nod, modulul diferentei intre numarul de noduri ale subarborelui stang si numarul de noduri ale subarborelui drept sa fie maxim 1.
Se dau Q intrebari de tipul “Cati arbori super-echilibrati cu N noduri exista?”. Deoarece numarul acestora poate ajunge destul de mare rezultatul se va calcula modulo 666013.
Date de intrare
Fişierul de intrare ciuperci.in contine pe prima linie Q, numarul de intrebari. Urmeaza Q linii. Pe linia i+1 se afla un numar Ni care reprezinta numarul de noduri pentru intrebarea i.
Date de ieşire
În fişierul de ieşire ciuperci.out contine Q numere, cate unul pe linie. Numarul de pe linia i reprezinta raspunsul la intrebarea i.
Restricţii
- 1 ≤ Q ≤ 105
- 1 ≤ Ni ≤ 1016
- a modulo b reprezinta restul impartirii lui a la b
- doi arbori sunt consideranti diferiti daca parcurgerea lor in inordine este diferita
- parcurgerea in inordine este parcurgerea dupa ordinea Fiu_stanga, Radacina, Fiu_dreapta
- Atentie! Se recomanda folosirea tipului long long pentru cei care implementeaza in C/C++ si int64 pentru cei care implementeaza in Pascal
Exemplu
| ciuperci.in | ciuperci.out |
|---|---|
| 4 1 2 4 5 | 1 2 4 4 |
Explicaţie
Pentru 1 avem doar radacina.
Pentru 2 avem radacina cu un fiu stang sau unul drept, deci 2 solutii.
