Cod sursa(job #501526)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 15 noiembrie 2010 16:22:45
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <stdio.h>
#include <algorithm>
using namespace std;

struct sum 
{
	int s, i1, i2, i3;
};

int N, S, NP;
int A[101], X[6];
sum P[200000];

int cmp (sum a, sum b)
{
	return a.s < b.s;
}

int cauta (int val)
{
	int p = 1, u = NP, m;
	while (p <= u)
	{
		m = p + (u - p) / 2;
		if (val >= P[m].s)
			p = m + 1;
		else
			u = m - 1;		
	}
	if (u < 1 || u > NP) return -1;
	return u;
}

void citire ()
{
	scanf ("%d%d", &N, &S);
	for (int i = 0; i < N; ++i)
		scanf ("%d", &A[i]);	
}

void back (int k)
{
	if (k == 4)
	{
		P[++NP].s = A[X[1]] + A[X[2]] + A[X[3]];
		P[NP].i1 = A[X[1]];
		P[NP].i2 = A[X[2]];
		P[NP].i3 = A[X[3]];
		return;
	}
	
	for (int i = X[k - 1]; i < N; ++i)
	{
		X[k] = i;
		back (k + 1);
	}	
}

void parcurgere ()
{
	int i, j, k, val, poz;
	for (i = 0; i < N; ++i)
		for (j = 0; j < N; ++j)
			for (k = 0; k < N; ++k)
			{
				val = S - (A[i] + A[j] + A[k]);
				poz = cauta (val);
				if (poz == -1) continue;
				if (P[poz].s == val)
				{
					X[0] = P[poz].i1;
					X[1] = P[poz].i2;
					X[2] = P[poz].i3;
					X[3] = A[i];
					X[4] = A[j];
					X[5] = A[k];
					
					return;
				}				
			}				
}

void afs ()
{
	if ( !X[5] ) printf ("-1");
	else
		for (int i = 0; i < 6; ++i)
			printf ("%d ", X[i]);
}

int main ()
{
	freopen ("loto.in", "r", stdin);
	freopen ("loto.out", "w", stdout);
	
	citire ();
	sort (A, A + N);
	back (1);
	sort (P + 1, P + NP + 1, cmp);
	parcurgere ();
	afs ();
	
	return 0;
}