Fişierul intrare/ieşire:ciuperci.in, ciuperci.outSursă.com 2011
AutorRadu Stefan VoroneanuAdăugată decezar305Mr. Noname cezar305
Timp execuţie pe test1.2 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/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.inciuperci.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content