Cod sursa(job #823620)

Utilizator IoannaPandele Ioana Ioanna Data 25 noiembrie 2012 13:13:38
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include<fstream>
#include<vector>
#define mod 1000007
using namespace std;

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

vector <long> v,h[mod+3];
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];
				if (sum<=s)
                    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)
				{
					out<<v[i]<<" "<<v[j]<<" "<<v[k]<<" ";
					w=3;
				}
            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]==s-sum)
				{
					out<<v[i]<<" "<<v[j]<<" "<<v[k]<<" ";
                    w=3;
				}

}

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

}