Cod sursa(job #1706924)

Utilizator RadoiuToniRadoiu Toni RadoiuToni Data 23 mai 2016 20:39:13
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("loto.in");
ofstream g("loto.out");

int main()
{
    int n, *v, *nrmin, *pmin, S, min, aux;
    f>>n>>S;
    v = new int[n+1];
    for(int i=1; i<=n; i++)
        f>>v[i];
    nrmin = new int[S+1];
    pmin = new int[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)
        cout<<-1;
    aux=S;
    while(aux>0)
    {
        g<<v[pmin[aux]]<<" ";
        aux=aux-v[pmin[aux]];
    }
    return 0;
}