Cod sursa(job #808748)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 7 noiembrie 2012 11:06:59
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <vector>
#define NMAX 1000009
#define DISP 666013

using namespace std;

ifstream in("loto.in");
ofstream out("loto.out");

struct _nr{int n1,n2,n3,val;}Sum[NMAX];

vector<pair<int,int> > Hash[DISP];

int N,S,V[102],M;

inline int Cauta(int nr)
{
	int d = nr%DISP, n = Hash[d].size();
	for(int i=0;i<n;i++)
		if(Hash[d][i].first == nr)
			return Hash[d][i].second;
	return 0;
}

inline void Adauga(int nr,int poz)
{
	if(Cauta(nr))return;
	Hash[nr%DISP].push_back(make_pair(nr,poz));
}

int main ()
{
	int i,j,k;
	in>>N>>S;
	for(i=0;i<N;i++)
		in>>V[i];
	for(i=0;i<N;i++)
		for(j=i;j<N;j++)
			for(k=j;k<N;k++)
			{
				Sum[++M].val = V[i]+V[j]+V[k],Sum[M].n1 = V[i],Sum[M].n2 = V[j],Sum[M].n3 = V[k];
				Adauga(Sum[M].val,M);
			}
	for(i=1;i<=M;++i)
	{
		k = Cauta(S - Sum[i].val);
		if( k )//am solutie
		{
			out<<Sum[i].n1<<' '<<Sum[i].n2<<' '<<Sum[i].n3<<' '<<Sum[k].n1<<' '<<Sum[k].n2<<' '<<Sum[k].n3<<'\n';
			return 0;
		}
	}
	out<<"-1\n";
	return 0;
}