Cod sursa(job #429694)

Utilizator nandoLicker Nandor nando Data 30 martie 2010 13:14:00
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

#define HASH 666013
#define MAX 105

struct tri{
	int i,j,k,sum;
	
};

typedef vector<pair<int,int> >::iterator iter;

vector<pair<int,int> > hash[HASH];
vector<tri> s;
int n,sum,nr[MAX];

iter findHash(int suma){
	int a=suma%HASH;
	for(iter it=hash[a].begin();it!=hash[a].end();it++){
		if(it->second==suma){
			return it;
		}
	}
	return hash[a].end();
}

void addHash(pair<int,int> e){
	int a=e.second%HASH;
	if(findHash(e.second)==hash[a].end()){
		hash[a].push_back(e);
	}
}
int findID(int s){
	iter it=findHash(s);
	if(it!=hash[s%HASH].end()){
		return it->first;
	}else{
		return -1;
	}
}
int main(){
	FILE* fin=fopen("loto.in","r");
	freopen("loto.out","w",stdout);

	fscanf(fin,"%d %d ",&n,&sum);

	for(int i=0;i<n;i++){
		fscanf(fin,"%d ",&nr[i]);
	}
	
	sort(nr,nr+n);
	bool fnd=false;

	for(int i=0;i<n&&!fnd;i++){
		for(int j=0;j<n&&!fnd;j++){
			for(int k=0;k<n&&!fnd;k++){
				tri t;
				t.i=i,t.j=j,t.k=k,t.sum=nr[i]+nr[j]+nr[k];
				addHash(make_pair(s.size(),t.sum));
				s.push_back(t);
				int l=findID(abs(sum-t.sum));
				if(l>=0){
					printf("%d %d %d %d %d %d\n",nr[t.i],nr[t.j],nr[t.k],
												 nr[s[l].i],nr[s[l].j],nr[s[l].k]);
					fnd=true;
				}
			}
		}
	}
	if(!fnd){
		printf("-1\n");
	}
	fclose(fin);
	return 0;
}