Cod sursa(job #610615)

Utilizator SteveStefan Eniceicu Steve Data 28 august 2011 12:15:33
Problema Loto Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <fstream.h>

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

typedef struct elem
{
	long Suma;
	long unu;
	long doi;
	long trei;
};

long i, N, S, vector[110], l = -1, gata = 0, max = -1;
elem v[1000010], auxil;

void qsort (long l1, long l2)
{
	long l1a = l1, l2a = l2, pivot = 0;
	if (l1 >= l2) return;
	while (l1 < l2)
	{
		if (v[l1].Suma > v[l2].Suma)
		{
			memcpy (&auxil, &v[l1], sizeof (elem));
			memcpy (&v[l1], &v[l2], sizeof (elem));
			memcpy (&v[l2], &auxil, sizeof (elem));
			if (pivot)
			{
				l2--;
				pivot = 0;
			}
			else
			{
				l1++;
				pivot = 1;
			}
		}
		else
		{
			if (pivot) l1++;
			else l2--;
		}
	}
	qsort (l1a, l1 - 1);
	qsort (l1 + 1, l2a);
}

int cautare_binara (int val)
{
	long h, step;
	for (step = 1; step < l; step <<= 1);
	for (h = 0; step; step >>= 1)
	{
		if (h + step < l && v[h + step].Suma <= val) h += step;
	}
	return h;
}

int main ()
{
	fin >> N >> S;
	for (i = 0; i < N; i++)
	{
		fin >> vector[i];
		if (vector[i] > max) max = vector[i];
	}
	fin.close ();
	if (max * 6 < S)
	{
		fout << "-1";
		fout.close ();
		return 0;
	}
	long j, k;
	for (i = 0; i < N; i++)
	{
		for (j = i; j < N; j++)
		{
			for (k = j; k < N; k++)
			{
				v[++l].unu = vector[i];
				v[l].doi = vector[j];
				v[l].trei = vector[k];
				v[l].Suma = v[l].unu + v[l].doi + v[l].trei;
			}
		}
	}
	qsort (0, l);
	long aux;
	long gasit;
	for (i = 0; i <= l; i++)
	{
		aux = S - v[i].Suma;
		gasit = cautare_binara (aux);
		if (v[gasit].Suma == aux)
		{
			fout << v[i].unu << " " << v[i].doi << " " << v[i].trei << " " << v[gasit].unu << " " << v[gasit].doi << " " << v[gasit].trei;
			fout.close ();
			return 0;
		}
	}
	fout << "-1";
	fout.close ();
	return 0;
}