# PBinfo #1706 – Stele – Rezolvare C++

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

## Enunț

Pasionată de astronomie, Teodora dorește să țină evidența numărului de stele din galaxii. Pentru a face lucrurile mai interesante, ea codifică aceste numere într-un sistem propriu, transformându-le într-o înșiruire de litere și cifre după algoritmul următor: 

notează fiecare putere a lui 2, strict mai mică decât 226, cu o literă a alfabetului, astfel:



 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 210 
 211 
 212 


 a 
 b 
 c 
 d 
 e 
 f 
 g 
 h 
 i 
 j 
 k 
 l 
 m 


 213 
 214 
 215 
 216 
 217 
 218 
 219 
 220 
 221 
 222 
 223 
 224 
 225 


 n 
 o 
 p 
 q 
 r 
 s 
 t 
 u 
 v 
 w 
 x 
 y 
 z 



reprezintă fiecare număr ca un șir de cifre și litere obținut din scrierea acelui număr ca sumă de puteri ale lui 2; dacă o putere este folosită de mai multe ori în descompunerea numărului atunci ea va fi precedată în șir de numărul de utilizări.

Un număr poate fi reprezentat astfel în mai multe moduri. De exemplu, pentru numărul 100 printre variantele de reprezentare avem:


100 = cfg = 22+25+26 = 4+32+64 = 100
100 = 2ab2cde2f = 2*20+21+2*22+23+24+2*25 = 2*1+2+2*4+8+16+2*32 = 100
100 = 16bcg = 16*21+22+26 = 16*2+4+64 = 100

Cerința
Scrieți un program care rezolvă următoarele cerinţe:


cunoscând s numărul de stele dintr-o galaxie, determină o reprezentare codificată a acestui număr formată doar din litere mici distincte ordonate alfabetic;
cunoscând g, reprezentând numărul de galaxii și g numere în scriere codificată, reprezentând numărul de stele din fiecare galaxie, determină scrierea zecimală a numărului total de stele din cele g galaxii.

Date de intrare
Fișierul de intrare stele.in conține pe prima linie un număr natural c, reprezentând cerinţa care trebuie rezolvată (1 sau 2). Dacă cerinţa este 1, pe a doua linie se află un număr natural s, ce reprezintă numărul care trebuie codificat. 

Dacă cerinţa este 2, pe a doua linie se află un număr natural g reprezentând numărul de galaxii, iar pe următoarele g linii câte un șir de caractere reprezentând numărul de stele dintr-o galaxie, codificat folosind algoritmul descris mai sus.

Date de ieșire
Fișierul de ieșire stele.out va conţine o singură linie pe care va fi scris un șir de litere mici distincte, ordonate alfabetic, reprezentând scrierea codificată a numărului s (dacă cerinţa este 1) sau un număr natural în scriere zecimală ce reprezintă numărul total de stele din cele g galaxii (dacă cerinţa este 2).

Restricții și precizări

1 ≤ s ≤ 226-1
1 ≤ g ≤ 1000
Reprezentările codificate din fişierul de intrare pot avea maximum 420 caractere.
Numărul care poate apărea în fața unei litere poate avea maximum 15 cifre.
Pentru teste valorând 30% din punctaj cerinţa este 1.
Pentru teste corespunzătoare cerinţei 2 valorând 20% din punctaj valoarea obținută nu depășește 1018

Exemplul 1
stele.in

1
100
stele.out

cfg
Explicație
Cerința este 1. Reprezentarea numărului 100  care respectă cerinţa este: cfg = 22+25+26 = 4+32+64 = 100

Exemplul 2
stele.in

2
5
2a7g
17b5d14g
100a2000b
7e15f
2d6f
stele.out

6320
Explicație
Cerința este 2 și avem 5 numere:


2a7g = 450
17b5d14g = 970
100a2000b = 4100
7e15f = 592
2d6f = 208

Suma lor este: 450 + 970 + 4100 + 592 + 208 = 6320

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
ifstream  fin("stele.in");
ofstream fout("stele.out");
long long v[26];
long long nr[26];
void cerinta1(int nr, char s[])
{
    char x;
    int i=0, j=0;
    while(i<25 && v[i]<=nr)i++;
    while(nr>0)
    {
        while(v[i]>nr)i--;
        s[j++]=i+'a';
        nr-=v[i];
    }
    s[j]=0;
    i=0;j--;
    while(i<j)
        x=s[i],s[i]=s[j],s[j]=x,i++,j--;
}
void numarare(char s[])
{
    int i=0;
    long long n=0;
    if(s[0]>='a' && s[0]<'z')
        nr[s[i]-'a']+=1, i=1;
    for(;s[i];i++)
        if(s[i]>='0' && s[i]<='9')
            n=n*10+s[i]-'0';
        else
            if(s[i-1]>='a' && s[i-1]<='z')
                nr[s[i]-'a']+=1;
            else
                nr[s[i]-'a']+=n, n=0;
}
void prod(long long nr, long long v, int rez[])
{
    int i;
    long long t=0;
    rez[0]=0;
    while(nr)
        rez[++rez[0]]=nr%10, nr/=10;
    for(i=1; i<=rez[0] || t; i++)
        t+=rez[i]*v, rez[i]=t%10, t/=10;
    rez[0]=i-1;
}
void add(int s[], int rez[])
{
    int i;
    long long t=0;
    for(i=1;i<=s[0] || i<=rez[0] || t; i++, t/=10)
        t+=s[i]+rez[i], s[i]=t%10;
    s[0]=i-1;
}
void suma()
{
    int s[101]={0}, rez[101], i, j;
    s[0]=1;
    s[1]=0;
    for(i=0;i<26;i++)
        if(nr[i])
        {
            for(j=0;j<100;j++)rez[j]=0;
            prod(nr[i], v[i], rez);
            add(s, rez);
        }
    for(i=s[0];i>=1;i--)
        fout<<s[i];
    fout<<'\n';
}
int main()
{
    int n, C, i, p=1;
    char s[500];
    for(i=0;i<26;i++)
        v[i]=p,p*=2;
    fin>>C>>n;
    if(C==1)
        cerinta1(n, s), fout<<s<<'\n';
    else
    {
        for(i=1;i<=n;i++)
            fin>>s, numarare(s);
        suma();
    }
	fin.close();
	fout.close();
    return 0;
}
```

## Resurse

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