Cod sursa(job #841612)

Utilizator SovStoStoicescu Mihail Cristian SovSto Data 24 decembrie 2012 15:22:02
Problema Loto Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>
using namespace std;
# define MOD 999983

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

int main()
{
	int n,i,j,k,s;
	ifstream f("loto.in");
	ofstream g("loto.out");
	f>>n>>s;
	int v[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->x + p->y + p->z;
			nod *q=combo[(s-sum1)%MOD];
			while(q)
			{
				int sum2 = q->x+q->y+q->z;
				if(sum1+sum2==s)
				{
					g<<p->x<<" "<<p->y<<" "<<p->z<<" "<<q->x<<" "<<q->y<<" "<<q->z<<" ";
					return 0;
				}
				q=q->adr;
			}
			p=p->adr;
		}
	}
	g<<"-1";
}