Cod sursa(job #841643)

Utilizator SovStoStoicescu Mihail Cristian SovSto Data 24 decembrie 2012 15:50:42
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>
using namespace std;

#define MOD 999983

struct nod
{
	int a,b,c;
	nod *adr;
} *combo[MOD];

void add(int x,int y,int z)
{
	int s=x+y+z;
	int m=s%MOD;
	if(!combo[m])
	{
		combo[m]=new nod;
		combo[m]->a = x;
		combo[m]->b = y;
		combo[m]->c = z;
		combo[m]->adr = NULL;
		return ;
	}
	nod *p=combo[m];
	while( p->adr && (p->a + p->b + p->c !=s )) p = p->adr;
	if(p->adr) return;
	p->adr = new nod;
	p->adr->a = x;
	p->adr->b = y;
	p->adr->c = z;
	p->adr->adr = NULL;
}


int main()
{
	int n,i,j,k,s,*v;
	ifstream f("loto.in");
	ofstream g("loto.out");
	f>>n>>s;
	v=new int[n];
	for(i=0;i<n;i++)
		f>>v[i];
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			for(k=0;k<n;k++)
				if(v[i] + v[j] + v[k] < s)
					add(v[i],v[j],v[k]);
	
	for(i=0;i<MOD;i++)
	{
		nod *p = combo[i];
		while(p)
		{
			int sum1 = p->a + p->b + p->c;
			nod *q=combo[(s-sum1)%MOD];
			while(q)
			{
				int sum2= q->a + q->b + q->c;
				if (sum1+sum2 == s )
				{
					g<<p->a<<" "<<p->b<<" "<<p->c<<" "<<q->a<<" "<<q->b<<" "<<q->c;
					return 0;
				}
				q=q->adr;
			}
			p=p->adr;
		}
	}
	g<<"-1";
	return 0;
}