Pagini recente » Cod sursa (job #3030947) | Cod sursa (job #2432570) | Cod sursa (job #11241) | Cod sursa (job #720762) | Cod sursa (job #1706928)
#include <iostream>
#include <fstream>
#include <limits.h>
using namespace std;
ifstream f("loto.in");
ofstream g("loto.out");
int main()
{
long long n, *v, *nrmin, *pmin, S, min, aux;
f>>n>>S;
v = new long long[n+1];
for(int i=1; i<=n; i++)
f>>v[i];
nrmin = new long long[S+1];
pmin = new long long[S+1];
nrmin[0]=0;
for(int i=1; i<=S; i++)
{
min = INT_MAX;
for(int j=1; j<=n; j++)
if(v[j]<=i && 1+nrmin[i-v[j]]<min)
{
min=1+nrmin[i-v[j]];
aux=j;
}
nrmin[i]=min;
pmin[i]=aux;
}
if(nrmin[S]==INT_MAX)
g<<-1;
else
{
aux=S;
while(aux>0)
{
g<<v[pmin[aux]]<<" ";
aux=aux-v[pmin[aux]];
}
}
return 0;
}