Lui Scortzy îi plac foarte mult bilele și puterile lui 3
, astfel și-a organizat colecția de bile în cutii, după următoarea regulă: în prima cutie a pus o bilă, în a doua cutie 3
bile, în a treia cutie 9
bile, apoi 27, 81, 243
, … ș.a.m.d. Privind linia lungă de cutii Scortzy și-a pus întrebarea: Ce număr de bile poate obține folosind bilele din cutii, fără a le scoate din cutie?
Pentru a răspunde întrebării a început să formeze numerele: 0
(nici o cutie), 1
(cutia 1
), 3
(cutia 2
), 4
(cutiile 1
și 2
), 9
(cutia 3
) … ș.a.m.d., obținând șirul lui Scortzy, primii termeni ai acestui șir fiind: 0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37
.
Plăcându-i noul șir obținut Scortzy dorește să rezolve următoarele probleme:
Cerința
1. Citind un număr natural n
determină câte cutii au mai puțin de n
bile în ele;
2. Citind un număr natural n
urmat de n
valori naturale x1, x2, ..., xn
determină câte bile sunt, în fiecare dintre cutiile utilizate, pentru a obține cel de-al xi
-lea număr din șirul lui Scortzy.
Date de intrare
Pe prima linie a fișierului puteri3.in
se află numerele naturale c
și n
, separate printr-un spațiu. Dacă c=2
atunci pe următoarele n
linii se vor găsi n
valori naturale x1, x2, ..., xn
, câte una pe linie, ce reprezintă pozițiile din șirul lui Scortzy.
Date de ieșire
Dacă c=1
atunci fișierul puteri3.out
va conține un singur număr care reprezintă soluția cerinței 1
, iar dacă c=2
atunci fișierul puteri3.out
va conține pe fiecare din cele n
linii ale sale unul sau mai multe numere. Pe linia i
a fișierului puteri3.out
se vor afla unul sau mai multe numere, separate prin câte un spațiu, în ordine crescătoare, ce reprezintă numărul de bile din fiecare cutie folosită pentru a obține numărul de pe poziția x_i
din șirul lui Scortzy.
Restricții și precizări
C ∈ {1, 2}
1 ≤ x1, x2, . . . , xn ≤ 10
18
- Pentru
c = 1
,1 ≤ n ≤ 10
18
- Pentru
c = 2
,1 ≤ n ≤ 1000
, numărul de bile dintr-o cutie nu are mai mult de80
de cifre. - Pentru 20 de puncte,
c = 1
- Pentru 30 de puncte,
c = 2
,1 ≤ x1, x2, . . . , xn ≤ 1000
- Pentru 35 de puncte,
c = 2
, numărul de bile dintr-o cutie nu este mai mare decât10
18
- Pentru 15 de puncte,
c = 2
, fără restricții suplimentare.
Exemplul 1:
puteri3.in
1 100
puteri3.out
5
Explicație
Cutiile cu 1
, 3
, 9
, 27
și 81
bile au mai puțin de 100
de bile în ele.
Exemplul 2:
puteri3.in
2 3 4 14 9
puteri3.out
1 3 1 9 27 27
Explicație
Primii termeni ai șirului lui Scortzy sunt: 0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37
.
Termenul de pe poziția 4
are valoarea 4
și se obține din suma 1 + 3
.
Termenul de pe poziția 14
are valoarea 37
și se obține din suma 1 + 9 + 27
.
Termenul de pe poziția 9
are valoarea 27
și se obține folosind cutia ce conține 27
bile.