== 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. 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

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") ==