Cod sursa(job #678097)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 11 februarie 2012 00:13:32
Problema Loto Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <fstream>
#include <map>
#include <set>
#include <vector>
#include <list>
#include <stack>
using namespace std;

const char* infile = "loto.in";
const char* outfile = "loto.out";

#define HASH 100001
#define NMAX 101

int N;
int S;

int Nr[NMAX];
struct SumaInfo;


struct SumaInfo
{
	int sum;
	int nr[3];
	SumaInfo( int a = 0, int b = 0, int c = 0)
	{
		sum = a + b + c;
		this->nr[0] = a;
		this->nr[1] = b;
		this->nr[2] = c;
	}
};


ostream& operator << (ostream& stream, SumaInfo & sumaInfo)
{
	stream << sumaInfo.nr[0] << " "
		   << sumaInfo.nr[1] << " "
		   << sumaInfo.nr[2] << " ";
	return stream;
}


list<SumaInfo> L[HASH];
stack<SumaInfo> sume;


inline int CalcHash(int x)
{
	return x % HASH;
}


SumaInfo Find(int sum)
{
	int hash = CalcHash(sum);

	for (list<SumaInfo>::iterator itr = L[hash].begin();
		itr != L[hash].end();
		itr++)
	{
		if( itr->sum == sum)
			return (*itr);
	}

	return SumaInfo();
}

bool Exists(SumaInfo & si)
{
	int hash = CalcHash(si.sum);

	for (list<SumaInfo>::iterator itr = L[hash].begin();
		 itr != L[hash].end();
		 itr++)
	{
		if( itr->sum == si.sum)
			return true;
	}
	return false;

}

void CalcSume() 
{
	for(int i = 0 ; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			for (int k = 0; k < N ; k++)
			{
				
				SumaInfo si(Nr[i], Nr[j], Nr[k]);
				if( !Exists(si))
				{
					L[CalcHash(si.sum)].push_front(si);
					sume.push(si);
				}
			}
		}
	}
	
	fstream fout (outfile, ios::out);

	bool done = false;
	while(sume.empty() == false)
	{
		SumaInfo current = sume.top();
		sume.pop();

		SumaInfo gasit = Find(S - current.sum);

		if(gasit.sum != 0)
		{
			done = true;
			fout << current << gasit << "\n";
			break;
		}
	}

	if(done == false)
	{
		fout << "-1\n";
	}
	fout.close();
}

int main()
{
	fstream fin(infile, ios::in);

	fin >> N >> S;

	for (int i = 0; i < N ; i++)
	{
		fin >> Nr[i];
	}

	fin.close();
	
	CalcSume();


}