# PBinfo #4444 – puteri3_ONI – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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 ≤ 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 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ât 1018
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.

## Cod sursă C++

```cpp
///Florentina Ungureanu - Colegiul Național de Informatică Piatra-Neamț
#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
ifstream in("puteri3.in");
ofstream out("puteri3.out");
int c,p[80][105],l[80];
ull n,x;
void p3()
{
    p[0][0]=1;
    l[0]=1;
    for(int i=1; i<80; ++i)
    {
        l[i]=l[i-1];
        for(int j=0;j<l[i]; ++j)
            p[i][j]=p[i-1][j]*3;
        for(int j=0;j<l[i]; ++j)
        {
            p[i][j+1]+=p[i][j]/10;
            p[i][j]%=10;
        }
        if(p[i][l[i]]) l[i]++;
    }
}
void afis(ull x)
{
    int k = 0;
    do
    {
        if(x%2)
        {
            for(int i=l[k]-1;i>=0;--i)
                out<<p[k][i];
            out<<' ';
        }
        k++;
        x/=2;
    }while(x);
    out<<'\n';
}
int main()
{
    p3();
    in>>c>>n;
    if(c==1)
    {
        ull poz=0,i=1;
        while(i<n) i*=3,poz++;
        out << poz << '\n';
    }
    else
    for(int i=1;i<=n;++i)
        {
           in>>x;
           if(x==1) out<<"0\n";
           else afis(x-1);
        }
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4444)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4444/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4444/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)