Cod sursa(job #94752)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 25 octombrie 2007 10:43:40
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<stdio.h>
#include<stdlib.h>
#define N 1000000
struct qqq{
	int ii,jj,kk,ss;
};
int sol[3],s;
qqq w[N];
int n,v[100],q;
void termin(){
	fclose(stdin);
	fclose(stdout);
	exit(0);
}
int compar(const void *a, const void *b){
	qqq *aa=(qqq*)a, *bb=(qqq*)b;
	return aa->ss-bb->ss;
}
void eliminare(int &n,qqq v[100]){
	int i,m=1;
	for(i=1;i<n;++i)
		if(v[i].ss!=v[i-1].ss)
			v[m++]=v[i];
	n=m;
}
int caut(int x){
	int p=0,u=q-1,m;
	while(p<u){
		m=(p+u)/2;
		if(x<=w[m].ss)
			u=m;
		else
			p=m+1;
	}
	return w[p].ss==x?p:-1;
}
void back(int k,int sum){
	if(k>2){
		int p=caut(s-sum);
		if(p>=0){
			printf("%d %d %d %d %d %d\n",sol[0],sol[1],sol[2],w[p].ii,w[p].jj,w[p].kk);
			termin();
		}
		return;
	}
	for(int i=0;i<n;++i)
		if(sum+v[i]<=s){
			sol[k]=v[i];
			back(k+1,sum+v[i]);
		}
}
int main(){
	int i,j,k;
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	scanf("%d%d",&n,&s);
	for(i=0;i<n;++i)
		scanf("%d",&v[i]);
	for(i=0;i<n;++i)
		for(j=0;j<n;++j)
			for(k=0;k<n;++k){
				w[q].ii=v[i];
				w[q].jj=v[j];
				w[q].kk=v[k];
				w[q++].ss=v[i]+v[j]+v[k];
			}
	qsort(w,q,sizeof(w[0]),compar);
	eliminare(q,w);
	/*
	for(i=0;i<q;++i)
		printf("%d+%d+%d=%d\n",w[i].ii,w[i].jj,w[i].kk,w[i].ss);
	*/
	back(0,0);
	printf("-1\n");
	termin();
	return 0;
}