== include(page="template/taskheader" task_id="lift") ==
Poveste şi cerinţă...
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. 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.
h2. Date de intrare
Fişierul de intrare $lift.in$ ...
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
În fişierul de ieşire $lift.out$ ...
În fişierul de ieşire $lift.out$ se vor afişa *Q* linii. Linia *i* va conţine numărul minim de comenzi date de Vellipo pentru a ieşi din clădirea *i*, apoi un spaţiu, urmat de un şir de caractere *‘+’* şi *‘–’* (fără spaţii), ce corespund sensului comenzilor de deplasare, în ordinea efectuării lor. În acest şir, caracterul *‘+’* specifică o comandă de urcare iar caracterul *‘–’*, una de coborâre.
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
* Soluţia nu este unică. Orice soluţie corectă cu număr minim de comenzi este acceptată.
h2. Exemplu
table(example). |_. lift.in |_. lift.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3
2
5
-6
| 2 ++
4 +-++
5 ---+-
|
h3. Explicaţie
...
* 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)
== include(page="template/taskfooter" task_id="lift") ==
