Cod sursa(job #97718)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 8 noiembrie 2007 08:54:15
Problema Loto Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<stdio.h>
#include<stdlib.h>
#define N 200000
struct combin{
	int i,j,k,s;
};
int compar(const void *a,const void *b){
	combin *aa=(combin*)a,*bb=(combin*)b;
	return aa->s - bb->s;
}
int caut(int x,int q,combin w[N]){
	int p=0,u=q-1,m;
	while(p<u){
		m=(p+u)/2;
		if(x<=w[m].s)
			u=m;
		else
			p=m+1;
	}
	if(x==w[p].s)
		return p;
	return -1;
}
void rezolva(int n,int v[100],int s){
	combin w[N];
	int q=0,p;
	for(int i=0;i<n;++i)
		for(int j=i;j<n;++j)
			for(int k=j;k<n;++k){
				w[q].i=v[i];
				w[q].j=v[j];
				w[q].k=v[k];
				w[q++].s=v[i]+v[j]+v[k];
			}
	qsort(w,q,sizeof(w[0]),compar);
	for(int i=0;i<n;++i)
		for(int j=i;j<n;++j)
			for(int k=j;k<n;++k){
				p=caut(s-v[i]-v[j]-v[k],q,w);
				if(p!=-1){
					printf("%d %d %d %d %d %d\n",w[p].i,w[p].j,w[p].k,v[i],v[j],v[k]);
					return;
				}
			}
	printf("-1\n");
}
int main(){
	int n,s,v[100],i;
	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]);
	rezolva(n,v,s);
	fclose(stdin);
	fclose(stdout);
	return 0;
}