== include(page="template/taskheader" task_id="puteri-3") ==
Poveste și cerință...
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.
h2. Cerințe
# Citind un număr natural *n* determină câte cutii au mai puțin de *n* bile în ele;
# Citind un număr natural *n* urmat de *n* valori naturale *x[~1~]*, *x[~2~]*, ..., *x[~n~]* determină câte bile sunt, în fiecare dintre cutiile utilizate, pentru a obține cel de-al *x[~i~]*-lea număr din șirul lui Scortzy.
h2. Date de intrare
Fișierul de intrare $puteri-3.in$ ...
Pe prima linie a fișierului $puteri-3.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 *x[~1~]*, *x[~2~]*, ..., *x[~n~]*, câte una pe linie, ce reprezintă pozițiile din șirul lui Scortzy.
h2. Date de ieșire
În fișierul de ieșire $puteri-3.out$ ...
Dacă *c* = 1 atunci fișierul $puteri-3.out$ va conține un singur număr care reprezintă soluția cerinței 1, iar dacă *c* = 2 atunci fișierul $puteri4.out$ va conține pe fiecare din cele *n* linii ale sale unul sau mai multe numere. Pe linia i a fișierului $puteri4.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.
h2. Restricții
* $... ≤ ... ≤ ...$
• *c* ∈ {1, 2};
• 1 ≤ *x[~1~]*, *x[~2~]*, ..., *x[~n~]* ≤ 1018
• Pentru *c* = 1, 1 ≤ *n* ≤ 1018
• Pentru *c* = 2, 1 ≤ *n* ≤ 1000, numărul de bile dintr-o cutie nu are mai mult de 80 cifre.
|_. # |_. Punctaj |_. Restricții |
| 1
| 20
| *c* = 1
|
| 2
| 30
| *c* = 2, 1 ≤ *x[~1~]*, *x[~2~]*, ..., *x[~n~]* ≤ 1000
|
| 3
| 35
| *c* = 2, numărul de bile dintr-o cutie nu este mai mare decât 10[^18^]
|
| 4
| 15
| *c* = 2, fără restricții suplimentare
|
h2. Exemplu
h2. Exemple
table(example).
|_. puteri-3.in |_. puteri-3.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|_. puteri-3.in |_. puteri-3.out |_. Explicații |
| 1 100
| 5
| Cutiile cu 1, 3, 9, 27 și 81 bile au mai puțin de 100 de bile în ele
|
| 2 3
4
14
9
| 1 3
1 9 27
27
| 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
|
h3. Explicație
...
== include(page="template/taskfooter" task_id="puteri-3") ==
