Cod sursa(job #164933)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 24 martie 2008 22:59:41
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
/* Problema 027 din arhiva
   Programare dinamica
   Complexitate o(N*S)
   25 puncte
*/

#include<stdio.h>
#define N 101
#define S 600001

int w[S][8];

int main(){
    int n,s,i,aux,j,k,v[N];
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    scanf("%d%d",&n,&s);
    for (i=1;i<=n;++i)
        scanf("%d",&v[i]);
    for (i=1;i<=s-1;++i)
        for (j=1;j<=n;++j)
            if (w[i][0]+1<w[i+v[j]][0]){
               aux=i+v[j];
               w[aux][0]=w[i][0]+1;
               for (k=1;k<=w[aux][0]-1;++i)
                   w[aux][k]=w[i][k];
               w[aux][w[aux][0]]=v[j];
            }
    if (w[s][0]==6)
       for (k=1;k<=6;++i)
           printf("%d ",w[s][k]);
    else 
         printf("-1");
    return 0;
}