Se dau n cifre. Cu acestea trebuie să formăm k numere astfel încât suma acestor k numere să fie minimă. Singura condiţie pe care trebuie să o respectăm în formarea celor k numere este ca cifrele nule să nu se afle la începutul unui număr.

Cerința

Determinaţi suma minimă care se poate obţine prin construirea a k numere care să utilizeze toate cele n cifre.

Date de intrare

Fişierul cifre5.in conţine pe prima linie două valori naturale n şi k cu semnificaţia de mai sus. Pe a doua linie fişierul conţine n cifre separate prin câte un spaţiu.

Date de ieșire

Fişierul cifre5.out va conţine pe prima linie un singur număr care va reprezenta suma celor k numere construite.

Restricții și precizări

2 ≤ n ≤ 100.000
1 ≤ k ≤ 100
k ≤ n
cel puţin k cifre dintre cele n sunt nenule

Exemplu

cifre5.in

7 3
2 1 0 4 9 9 1

cifre5.out

Explicație

Cu cele 7 cifre trebuie să formăm 3 numere. Suma minimă care putem să o obţinem este 152 şi poate fi obţinută dacă construim numerele 19, 24 şi 109. Există şi alte posibilităţi de a construi cele trei numere.

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 cifre5:

#include<cstdio>
#include<vector>
#define Nr vector<int>
using namespace std;
Nr X[1001];
int n,k,i,c,cnt[11],S[1001];
Nr operator+(Nr,Nr);
void read(),solve(),afiseaza(Nr);
int main()
{
    read();
    solve();
    return 0;
}
void read()
{
    freopen("cifre5.in","r",stdin);
    freopen("cifre5.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&c);
        cnt[c]++;
    }
}
void solve()
{
    for(i=1,c=1;i<=k;)
    {
        if(!cnt[c]){c++;continue;}
        S[i]=c;cnt[c]--;n--;i++;
    }
    for(c=9,i=1;n;)
    {
        if(!cnt[c]){c--;continue;}
        X[i].push_back(c);cnt[c]--;n--;i++;if(i>k)i=1;
    }
    for(i=1;i<=k;i++)X[i].push_back(S[i]);
    //for(i=1;i<=k;i++)
    //  afiseaza(X[i]);
    for(i=k;i>1;i--)
        X[i-1]=X[i]+X[i-1];
    afiseaza(X[1]);
}
Nr operator+(Nr U,Nr V)
{
    Nr R;R.resize(0);
    int r=0;
    Nr::iterator iu,iv,ir;
    for(iu=U.begin(),iv=V.begin();iu!=U.end()&&iv!=V.end();iu++,iv++)R.push_back(*iu+*iv);
    for(;iu!=U.end();iu++)R.push_back(*iu);
    for(;iv!=V.end();iv++)R.push_back(*iv);
    for(ir=R.begin();ir!=R.end();ir++)
    {
        *ir+=r;r=0;
        if(*ir>9){*ir-=10;r=1;}
    }
    if(r)R.push_back(1);
    return R;
}
void afiseaza(Nr U)
{
    Nr::reverse_iterator iu;
    for(iu=U.rbegin();iu!=U.rend();iu++)
        printf("%d",*iu);
    printf("
");
}

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 Adresa de email .

Rezolvarea problemei #684 cifre5

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #684 cifre5 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!

Rezolvare completă PbInfo #684 cifre5