Cod sursa(job #348088)

Utilizator serbanlupulupulescu serban serbanlupu Data 13 septembrie 2009 22:45:11
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <ctime>

using namespace std;

#define PRIM 1000001

vector<int > H[PRIM];

int v[101];
int  nr_v;
int sum;
int stop=0;

bool check(int sum_aux)
{
	vector<int >::iterator it;

	for (it=H[sum_aux%PRIM].begin(); it<H[sum_aux%PRIM].end(); it++)
		if (*it==sum_aux)
			return 1;
	return 0;
}

void afisare(int sum_aux,int q, int w, int e)
{
	for (short i=1; i<=nr_v; ++i)
		for (short j=i; j<=nr_v; ++j)
			for (short k=j; k<=nr_v; ++k)
				if ( (v[i]+v[j]+v[k])==sum_aux )
				{
					fstream g("test.out", ios::out);
					g<<v[q]<<" "<<v[w]<<" "<<v[e]<<" "<<v[i]<<" "<<v[j]<<" "<<v[k]<<"\n";
					g.close();
					stop=1;
				}
}

void solve()
{
	fstream f("test.in", ios::in);
	f>>nr_v;
	f>>sum;
	for (short i=1; i<=nr_v; ++i)
		f>>v[i];

	for (short i=1; i<=nr_v; ++i)
		for (short j=i; j<=nr_v; ++j)
			for (short k=j; k<=nr_v; ++k)
			{
				int suma=v[i]+v[j]+v[k];
				if ( check(suma)==0 )
					H[suma%PRIM].push_back(suma);
			}

	for (short i=1; i<=nr_v; ++i)
		for (short j=i; j<=nr_v; ++j)
			for (short k=j; k<=nr_v; ++k)
			{ 
				int suma_aux=sum-v[i]-v[j]-v[k];
				if (suma_aux>0)
					if (check(suma_aux))
						afisare(suma_aux, i, j, k);
			}
	if (stop==0)
	{
		fstream g("test.out", ios::out);
		g<<"-1";
		g.close();
	}
}
/*
void generator()
{
	srand(time(0));
	fstream q("test.in", ios::out);
	int n=rand()%100;
	q<<n<<" "<<(rand()*rand())%600000<<"\n";
	cout<<"n="<<n<<"\n";
	for (int i=1; i<=n; ++i)
	{
		q<<(rand()*rand())%100000<<" ";
		cout<<i<<" ";
	}
	q.close();
}
*/
int main()
{
	double s=clock();
	solve();
	cout<<(clock()-s)/(double)CLOCKS_PER_SEC;
	return 0;
}