lift

Lift

Vellipo doreşte să viziteze întreg complexul Liftopolis, ce găzduieşte *Q* clădiri. Fiecare clădire are o singură uşă de intrare la nivelul 0 şi o singură uşă de ieşire, aflată la un nivel precizat. Orice clădire din complex are mai multe niveluri dispuse atât deasupra cât şi dedesubtul nivelului 0, niveluri la care se poate ajunge folosind un lift foarte interesant, care poate transporta o singură persoană la un moment dat. La intrarea în clădire, Vellipo va intra direct în lift, unde va da o succesiune cu număr minim de comenzi de urcare sau coborâre, pentru a ajunge la ieşire. Fiecare a *k*-a comandă va determina urcarea sau coborârea cu un număr de niveluri egal cu valoarea termenului de rang *k* din şirul lui Fibonacci. Vellipo trebuie să dea cel puţin o comandă când urcă în lift.

h2. Cerintă

h2. Cerinţă

Pentru fiecare dintre cele *Q* clădiri din Liftopolis, precizată prin nivelul la care se află uşa de ieşire din clădire, să se
determine numărul minim de comenzi precum şi comenzile pe care Vellipo le va da pentru a ajunge la nivelul de ieşire.

Pentru fiecare dintre cele *Q* clădiri din Liftopolis, precizată prin nivelul la care se află uşa de ieşire din clădire, să se determine numărul minim de comenzi precum şi comenzile pe care Vellipo le va da pentru a ajunge la nivelul de ieşire.

h2. Date de intrare

Fişierul de intrare $lift.in$ conţine pe prima linie un număr natural Q ce reprezintă numărul de clădiri. Pe fiecare
dintre următoarele *Q* linii se află câte un număr întreg N ce reprezintă nivelul la care se află uşa de ieşire din clădire.

Fişierul de intrare lift.in conţine pe prima linie un număr natural Q ce reprezintă numărul de clădiri. Pe fiecare dintre următoarele Q linii se află câte un număr întreg N ce reprezintă nivelul la care se află uşa de ieşire din clădire.

h2. Date de ieşire

h2. Restricţii

* 1 ≤ Q ≤ 50.000
* pentru 20% dintre teste |N| ≤ 55 si |Q| ≤ 40
* pentru 40% dintre teste |N| ≤ 5000 si |Q|≤ 50000
* pentru 100% dintre teste |N| ≤ 10 15 si |Q| ≤ 50000
* Şirul lui Fibonacci: f ~1~ =1, f ~2~ =1, iar termenul de rang n este construit cu ajutorul relaţiei f ~n~ =f ~n-1~ +f ~n-2~ , n≥3

* 1 ≤ *Q* ≤ 50.000
* pentru 20% dintre teste | *N* | ≤ 55 si | *Q* | ≤ 40
* pentru 40% dintre teste | *N* | ≤ 5000 si | *Q* |≤ 50000
* pentru 100% dintre teste | *N* | ≤ 10^15^ si | *Q* | ≤ 50000
* Şirul lui Fibonacci: f ~1~ = 1, f ~2~ = 1, iar termenul de rang n este construit cu ajutorul relaţiei f ~n~ = f ~n-1~ + f ~n-2~ , n≥3
* Soluţia nu este unică. Orice soluţie corectă cu număr minim de comenzi este acceptată.

h2. Exemplu

* Pentru a ajunge la nivelul 2, numărul minim de comenzi date de Vellipo este 2: urcare, urcare (+1+1=2)
* Pentru a ajunge la nivelul 5, numărul minim de comenzi este 4: urcare, coborâre, urcare, urcare (+1-1+2+3=5)

* Pentru a ajunge la nivelul –6, numărul minim de comenzi este 5: coborâre, coborâre, coborâre, urcare, coborâre (+1+1+2-3+5=6)

* Pentru a ajunge la nivelul -6, numărul minim de comenzi este 5: coborâre, coborâre, coborâre, urcare, coborâre (+1+1+2-3+5=6)

== include(page="template/taskfooter" task_id="lift") ==