Cod sursa(job #355541)

Utilizator andrei.sfrentSfrent Andrei andrei.sfrent Data 11 octombrie 2009 15:17:11
Problema Loto Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>
#include <cstdlib>

using namespace std;

#define MAXN 100


int n, v[MAXN], sume[MAXN * MAXN * MAXN];
int ns, s;

ofstream fo("loto.out");

void citeste()
{
	ifstream fi("loto.in");
	fi >> n >> s;
	for(int i = 0; i < n; ++i)
		fi >> v[i];
	fi.close();
}

int fcmp(const void* a, const void* b)
{
	return (*((int*)a)) - (*((int*)b));
}

void refacereSuma(int x)
{
	int i, j, k;

	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] == x)
				{
					fo << v[i] << " " << v[j] << " " << v[k] << " ";
					return;
				}
			}
		}
	}
}

void rezolva()
{
	int i, j, k;

	//generare sume
	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)
					sume[ns++] = v[i] + v[j] + v[k];
	
	//sortare sume
	qsort(sume, ns, sizeof(int), fcmp);

	//caut doua sume partiale cu suma s
	j = ns - 1;
	for(i = 0; i <= j; ++i)
	{
		while(sume[i] + sume[j] > s) j--;
		if(sume[i] + sume[j] == s)
		{
			refacereSuma(sume[i]);
			refacereSuma(sume[j]);
			return;
		}
	}
	fo << "-1";
}

int main()
{
	citeste();
	rezolva();
	fo << "\n";
	fo.close();
	return 0;
}