# PBinfo #684 – cifre5 – Rezolvare C++

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

## Enunț

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

152
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.

## Cod sursă C++

```cpp
#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("\n");
}
```

## Resurse

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