Fişierul intrare/ieşire:	lift.in, lift.out	Sursă	Concursul Naţional de Informatică Urmaşii lui Moisil 2017
Autor	Valentin Rosca	Adăugată de	Valentin Rosca •valiro21
Timp execuţie pe test	0.5 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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.

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.

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.

Date de ieşire

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

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¹⁵ si | Q | ≤ 50000
• Şirul lui Fibonacci: f ₁ = 1, f ₂ = 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ă.

Exemplu

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)

Cum se trimit solutii?