Question

Maia tocmai a învăţat la şcoală să facă adunări cu numere naturale având mai multe cifre. Pentru că îi place foarte mult matematica s-a apucat să scrie pe o foaie multe numere naturale, cu una sau mai multe cifre, şi a început să le adune.

După o vreme s-a cam plictisit şi s-a gândit să afle cea mai mare sumă ce s-ar putea obţine dacă s-ar schimba între ele cifrele numerelor de pe foaie. Are însă o singură dorinţă: după ce schimbă cifrele între ele să rămână acelaşi număr de numere cu o cifră, acelaşi număr de numere cu două cifre şi aşa mai departe.

Cerinţe
Scrieţi un program care să determine

a) suma maximă ce se poate obţine schimbând între ele cifrele numerelor iniţiale;
b) un şir de numere pentru care se obţine suma maximă, respectând restricţiile din enunţ.

Date de intrare
Fișierul de intrare cifre9.in conține pe prima linie un număr natural n reprezentând numărul de numere scrise de Maia pe foaie. Următoarele n linii conţin cele n numere naturale scrise iniţial pe foaie, câte un număr pe fiecare linie.

Date de ieșire
Fișierul de ieșire cifre9.out va conține pe prima linie pe prima linie un număr natural S reprezentând suma maximă obţinută. Pe următoarele n linii vor fi scrise n numere naturale, câte un număr pe o linie, reprezentând un şir de numere pentru care se obţine suma maximă, respectând restricţiile din enunţ.

Restricții și precizări
2 ≤ n ≤ 100 000
Numerele din şirul iniţial sunt numere naturale ≤ 2^30-1
Numerele din şirul afişat nu vor conţine zerouri nesemnificative.
Dacă există mai multe şiruri pentru care se obţine suma maximă conform restricţiilor din enunţ, se va afişa oricare dintre acestea.
Pentru afişarea corectă a sumei maxime se acordă 40% din punctaj, punctajul integral obţinându-se pentru rezolvarea corectă a ambelor cerinţe.

Exemplu
cifre9.in

8
3120
400
1000
50
1
0
37
60
cifre9.out

14280
6410
500
10
20
10
0
7330
0
Explicație
Se observă că atât în şirul iniţial, cât şi în cel final sunt 2 numere de 4 cifre, un număr de 3 cifre, 3 numere de două cifre şi două numere de o cifră.

De asemenea, numerele din şirul afişat conţin în total aceleaşi cifre ca numerele din şirul din fişierul de intrare.

Suma maximă care se poate obţine este 14280.

Answer 1

#include <fstream>
#define NMAX 100001
#define LGMAX 20
using namespace std;
ifstream fin("cifre9.in"); ofstream fout("cifre9.out");
int n;
long long int smax;
int nr[LGMAX], s[LGMAX]; //nr[i]=numarul de numere cu i cifre
int nrc[10]; //nrc[i]=numarul de cifre i folosite in scrierea celor n numere
int v[NMAX][LGMAX],lg[NMAX];
int main()
{   int i, j, c, x, lgx;
    fin>>n;
    for(i=0;i<n;i++)
    {   fin>>x;
        lgx=0;
        do {nrc[x%10]++; lgx++; x/=10;} while(x);
        nr[lgx]++;
    }
    s[1]=1;
    for(i=2;i<LGMAX;i++) s[i]=s[i-1]+nr[i-1];
    //numerele de i cifre sunt plasate in v de la s[i] la s[i]+nr[i]-1;
    //plasez zerourile necesare in numere de o cifra
    for(i=1;i<=nr[1] && nrc[0]; i++) {nrc[0]--; lg[i]=1;}
    //plasez celelalte zerouri in mod echilibrat, pana le epuizez
    for(i=1;i<LGMAX-1;i++) //plasez zerouri pe pozitia i
    {   if(!nrc[0]) break;
        for(j=s[i+1]; j<=n && nrc[0]; j++) {lg[j]++; nrc[0]--;}
    }
    //distribui cifrele descrescator
    c=9;
    for(i=LGMAX-1;i>=0;i--) //plasez cifra c pe pozitia i in numerele pentru care exista cifra i disponibila
        for(j=s[i];j<=n;j++)
        {   while(!nrc[c]) c--;
            if(lg[j]<i) {nrc[c]--; v[j][i]=c;}
        }
    //construiesc numerele si calculez suma
    for(i=1;i<=n;i++) //construiesc numarul v[i]
    {   lg[i]=0;
        for(j=LGMAX-1;j;j--) lg[i]=lg[i]*10+v[i][j];
     smax+=lg[i];
    }
    fout<<smax<<'\n';
    for(i=1;i<=n;i++) fout<<lg[i]<<'\n';
    fout.close(); return 0;
}