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.
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema Cifre9:
//Carmen Popescu - 100 puncte
#include <fstream>
using namespace std;
int nr[10], // nr[k] = numarul de cifre k din toate numerele date
m, // numarul maxim de cifre
a[9][10][10], // a[i][j][k] numarul de numere de j cifre
// care contin pe pozitia i
// cifra k
t[10], // t[k] numarul de numere avand k cifre
b[10][10], // b[i][j] = numarul de numere cu j cifre care nu au inca
// completata cifra de pe pozitia i
sum[10000]; // suma numerelor finale, numar mare
// sum[0] cifra unit, sum[1]=cifra zecilor etc
ifstream fin("cifre9.in");
ofstream fout("cifre9.out");
void citire()
{
int x,k,n,i;
fin>>n;
for (i=0;i<n;i++)
{
fin>>x;
if (x==0)
{
nr[0]++;
t[1]++;
}
else
{
k=0;
while (x>0)
{
nr[x%10]++;
x=x/10;
k++;
}
t[k]++;
if (k>m)
m=k;
}
}
}
int minim(int &a,int &b)
{
int m;
m=a;
if (b<m)
m=b;
a=a-m;
b=b-m;
return m;
}
void distrib()
{
int i,j,k,p,q,mx=0;
for (i=0;i<=m;i++)
for (j=i+1;j<=m;j++)
b[i][j]=t[j];
// 0 la cifra unitatilor
k=0;
for (j=1;j<=m && nr[0]>0;j++)
a[0][j][0]=minim(b[0][j],nr[0]);
// 0 la cifra de pe pozitia i (i=1, cifra zecilor, i=2 cifra sutelor ect)
// ATENTIE! numerele de q cifre nu pot avea pe pozitia q-1 cifra 0
for (i=1;i<=m && nr[0]>0;i++)
for (j=i+2;j<=m;j++)
a[i][j][0]=minim(b[i][j],nr[0]);
// distribuim celelalte cifre (cifrele diferite de 0)
for (k=1;k<=9;k++) // cifra
for (i=0;i<m && nr[k]>0;i++) // pozitia
for (j=i+1;j<=m && nr[k]>0;j++) // nr de cifre
{
q=minim(b[i][j],nr[k]);
if (t>0)
{
a[i][j][k]=q;
sum[i]+=q*k; // cifra k apare de q
// ori pe pozitia i
// => k*q pe pozitia i in suma
p=i; // verificam transportul
while (sum[p]>9)
{
q=sum[p]/10;
sum[p]=sum[p]%10;
p++;
sum[p]+=q;
if (p>mx) // mx numarul de cifre din suma
mx=p;
}
}
}
for (i=mx;i>=0;i--)
fout<<sum[i];
fout<<"\n";
}
void constr()
{
int i,j,c,nr,p=0;
for (j=m;j>=1;j--) // numarul de cifre
while (t[j]>0) // numarul de numere cu j cifre
{
nr=0;
for (i=j-1;i>=0;i--)
{
c=9;
while (a[i][j][c]==0)
c--;
nr=nr*10+c;
a[i][j][c]--;
}
fout<<nr<<'\n';
p=1;
t[j]--;
}
}
int main()
{
citire();
distrib();
constr();
return 0;
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #1207 Cifre9
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1207 Cifre9 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!