Cod sursa(job #200700)

Utilizator mordredSimionescu Andrei mordred Data 25 iulie 2008 18:59:09
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<stdio.h>
#include<stdlib.h>
int v[1<<20],w[1<<7],x,s,n;
int pp(const void *a, const void *b){
	return *(int *)a-*(int *)b;
}
void write(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 search(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,aux=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),pp);
	for(i=0;i<x&&aux;++i){
		q=search(i,x-1);
		if(v[i]+v[q]==s){
			write(v[i]);
			write(v[q]);
			aux=0;
		}
	}
	
	if(aux)
		printf("-1\n");
	return 0;
}