Cod sursa(job #2200407)

Utilizator IustinPetrariuIustinian Petrariu IustinPetrariu Data 1 mai 2018 12:09:30
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <iostream>
#include <fstream>
#define NMAX 101

using namespace std;
ifstream fin("loto.in");
ofstream fout("loto.out");
int N,S,k,nr,b[NMAX],a[NMAX];
int suma,viz[NMAX];
int main()
{
    fin>>N>>S;
    for(int i =1 ; i <= N; i++)
    {
        fin>>a[i];
        suma+=a[i];
    }
    if(suma < S)
    {
        fout<<-1;
        return 0;
    }
    for(int i =1 ; i<= S; i++)
        b[i]=N+1;
    for(int i = 1; i <= N && b[S]==N+1; i++)
        for(int j = 0 ; j + a[i] <= S; j++)
           if(b[j] < i && b[j+a[i]]==N+1)
              b[j+a[i]]=i;
     if(b[S]==N+1)
     {
         fout<<-1;
         return 0;
     }
     else
     {
         int q;
         nr=0;
         k=S;
         do
         {
             nr++;
             q=b[k];
             viz[q]=1;
             k=k-a[q];

         }while(k>0);
         if(nr==6)
         {
             for(int i =1 ; i <= N; i++)
                if(viz[i]) fout<<a[i]<<" ";
         }
     }



    return 0;
}