Cod sursa(job #184115)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 23 aprilie 2008 06:16:49
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 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;
}