Cod sursa(job #184174)

Utilizator TociToxAnonim Anonim TociTox Data 23 aprilie 2008 11:42:59
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include<stdio.h>   
  
int main()   
{   
int s,v[101]={0},sm,da=0,sp;   
int n,i,j,k,t,li[7]={1},ls[7]={0};   
int x[7]={0},up;   
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<=n;i++)   
    for(j=i+1;j<=n;j++)   
        if(v[i]>v[j]) {t=v[i];v[i]=v[j];v[j]=t;}   
if(6*v[1]>s||6*v[n]<s) {printf("-1");return 0;}   
//calcul limite   
for(i=1;i<=6;i++){   
    k=li[0];   
    while(k<n&&((6-i)*v[n]+(i-1)*v[1]+v[k]<s)) k++;   
    li[i]=k;   
    if(li[i]>1&&((6-i)*v[n]+(i-1)*v[1]+v[k]>s)) li[i]--;   
    }   
ls[0]=n;   
for(i=1;i<=6;i++){   
    k=ls[0];   
    while(k>0&&((7-i)*v[k]+(i-1)*v[1]>s)) k--;   
    ls[i]=k;   
    if(ls[i]<n) ls[i]++;   
    }   
//initializari   
for(k=1;k<6;k++) x[k]=li[k];   
k=6;x[k]=li[6]-1;   
//backtracking   
while(k){   
    up=0;   
    if(x[k]<ls[k]) {   
                x[k]++;   
                up=1;   
               }   
  
    if(up)   
        if(k==6) {  sm=0;   
                    for(i=1;i<=6;i++) sm+=v[x[i]];   
                    if(sm==s) {da=1;break;}   
                    if(sm>s) k--;   
                 }   
        else {k++;j=x[k-1]-1;   
            sp=0;for(i=1;i<k;i++) sp+=v[x[i]];   
            while(j<n-1&&(6-k)*v[n]+sp+v[j]<s) j++;   
            if(j>x[k-1]) j=j-2;   
            else j=x[k-1]-1;   
            x[k]=j;   
           /*   j=x[k]+1;  
            while(j<n&&(7-k)*v[x[j]]+sp<s) j++;  
            ls[k]=j; */  
        }   
    else k--;   
}   
if(da)   
    for(i=1;i<=6;i++) printf("%d ",v[x[i]]);   
else  
    printf("-1");   
return 0;   
}