Cod sursa(job #808782)

Utilizator IoannaPandele Ioana Ioanna Data 7 noiembrie 2012 11:44:07
Problema Loto Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include<fstream>
#include<vector>
#define mod 666013
using namespace std;

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

vector <long> v,h[mod+1];
long n,s,mx;

void scan()
{
	long a;
	in>>n>>s;
	for (int i=1;i<=n;i++)
	{
		in>>a;
		v.push_back(a);
	}
}

void add(long sum)
{
	long i,k;
	k=sum%mod;
	if (k>mx)
		mx=k;
	for (i=0;i<h[k].size();i++)
		if (h[k][i]==sum)
			return;
	h[k].push_back(sum);

}

void sume()
{
	int i,j,k;
	long sum;
	for (i=0;i<n;i++)
		for (j=0;j<n;j++)
			for (k=0;k<n;k++)
			{
				sum=v[i]+v[j]+v[k];
				add(sum);
			}
}

int found(long sum)
{
	int i,k;
	k=sum%mod;
	for (i=0;i<h[k].size();i++)
	{
		if (h[k][i]==sum)
			return 1;
	}
	return 0;
}
long solve()
{
	int i,j,k;
	for (i=0;i<=mx;i++)
	{
		for (j=0;j<h[i].size();j++)
		{
			if (found(s-h[i][j]))
				return h[i][j];
		}
	}
	return -1;
}

void solutie(long sum)
{
	int i,j,k,w;
	w=0;
	for (i=0;i<n && w!=3;i++)
		for (j=0;j<n && w!=3;j++)
			for (k=0;k<n && w!=3;k++)
				if (v[i]+v[j]+v[k]==sum && w!=1)
				{
					out<<v[i]<<" "<<v[j]<<" "<<v[k]<<" ";
					w+=1;
				}
				else if (v[i]+v[j]+v[k]==s-sum && w!=2)
				{
					out<<v[i]<<" "<<v[j]<<" "<<v[k]<<" ";
					w+=2;
				}
}

int main()
{
	long w;
	scan();
	sume();
	w=solve();
	if (w!=-1)
		solutie(w);
	else out<<"-1\n";
	return 0;
	
}