Cod sursa(job #175202)

Utilizator MirageRobert Sandu Mirage Data 9 aprilie 2008 18:03:24
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<stdio.h>
#include<stdlib.h>
int v[1000000],w[100],x,s,n;
int comp(const void *a, const void *b){
	return *(int *)a-*(int *)b;
}
void scrie(int a){
	int i,j,k;
	for(i=0;i<n;++i)
		for(j=i;j<n;++j)
			for(k=j;k<n;++k)
				if(w[i]+w[j]+w[k]==a){
					printf("%d %d %d ",w[i],w[j],w[k]);
					return;
				}
}
int caut(int i,int u){
	int p,m;
	p=0;
	while(p<u){
		m=(p+u)/2;
		if(s<=v[i]+v[m])
			u=m;
		else
			p=m+1;
	}
	return p;
}
int main(){
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	int i,j,q,mda=1,k;
	scanf("%d%d",&n,&s);
	for(i=0;i<n;++i)
		scanf("%d",&w[i]);
	x=0;
	for(i=0;i<n;++i){
		for(j=i;j<n;++j){
			for(k=j;k<n;++k){
				v[x]=w[i]+w[j]+w[k];
				++x;
			}
		}
	}
	qsort(v,x,sizeof(int),comp);
	for(i=0;i<x&&mda;++i){
		q=caut(i,x-1);
		if(v[i]+v[q]==s){
			scrie(v[i]);
			scrie(v[q]);
			mda=0;
		}
	}
	
	if(mda)
		printf("-1\n");
	return 0;
}