Cod sursa(job #202197)

Utilizator piroslPiros Lucian pirosl Data 6 august 2008 19:38:37
Problema Loto Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include<iostream>
using namespace std;

struct node 
{
	int s;
	int i1,i2,i3;
	struct node *left;
	struct node *rigth;
};

int numere[101];

void add(node*& dest, node* n)
{
	if(dest == NULL)
	{
		dest = n;
	}
	else 
	{
		if(n->s < dest->s)
			add(dest->left, n);
		if(n->s > dest->s)
			add(dest->rigth, n);
	}
}

void parc(node* n)
{
	if(n == NULL)
		return;
	parc(n->left);
	cout << n->s << " " << n->i1 << " " << n->i2 << " " << n->i3 << endl;
	parc(n->rigth);
}

node* cauta(node* n, int s)
{
	if(n == NULL)
		return NULL;
	if(s == n->s)
		return n;
	if(s < n->s)
		return cauta(n->left, s);
	return cauta(n->rigth, s);
}

bool solutie(node* head, node* n, int s)
{
	if(n == NULL)
		return false;

	int s1 = n->s;
	node* tmpNode = cauta(head, s-s1);
	if(tmpNode != NULL)
	{
		cout << n->i1 << " " << n->i2 << " " << n->i3 << " " << tmpNode->i1 << " " << tmpNode->i2 << " " << tmpNode->i3 << endl;
		return true;
	}
	if(solutie(head, n->left, s))
		return true;

	return solutie(head, n->rigth, s);
}

int main(void)
{
	node* head = NULL;
	int n, s;
	freopen("loto.in", "r", stdin);
	freopen("loto.out", "w", stdout);
	cin >> n >> s;
	for(int i = 0;i<n;++i)
		cin >> numere[i];
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<n;++j)
		{
			for(int k=0;k<n;++k)
			{
				node* nod = new node();
				nod->i1 = numere[i];
				nod->i2 = numere[j];
				nod->i3 = numere[k];
				nod->s = nod->i1 + nod->i2 + nod->i3;
				nod->left = NULL;
				nod->rigth = NULL;
				add(head, nod);
			}
		}
	}

	//parc(head);
	if(!solutie(head, head, s))
		cout << -1 << endl;
	return 0;
}