Cod sursa(job #451035)

Utilizator miculprogramatorA Cosmina - vechi miculprogramator Data 8 mai 2010 21:06:48
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <stdio.h>
#include <algorithm>
using namespace std;

struct loto
{
	long int a;
	long int b;
	long int c;
	long int sum;
};

long int nr[101];
long int S, s_aux;
long int n, i, j, k, l = 1, p;
long int poz, ok;
loto v[500000], a, b;

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

int main ()
{
	FILE *f = fopen ("loto.in","r");
	FILE *g = fopen ("loto.out","w");
	fscanf (f,"%ld %ld", &n, &S);
	for (i=1; i<=n; ++i)
		fscanf (f,"%ld", &nr[i]);
	fclose(f);
	
	for (i=1; i<=n; ++i)
		for (j=i; j<=n; ++j)
			for (k=j; k<=n; ++k)
			{
				v[l].a = nr[i];
				v[l].b = nr[j];
				v[l].c = nr[k];
				v[l].sum = nr[i] + nr[j] + nr[k];
				l ++;
			}
	
	//printf ("l = %d", l);
	sort (v + 1, v + l, cmp);
	for (p=1; p * 2 <= l-1; p *= 2);
	
	for (i=1; i<=l-1; ++i)
	{
		k = p;
		b = v[i];
		s_aux = S - b.sum;
		for (poz=0; k; k /= 2)
		{
			if (poz + k <= l - 1)
				if (v[k + poz].sum <= s_aux)
					poz += k;
		}
		if (v[poz].sum == s_aux)
		{
			ok = 1;
			a = v[poz];
			break;
		}
	}
	
	if (ok)
	{
		fprintf (g,"%ld %ld %ld %ld %ld %ld", b.a, b.b, b.c, a.a, a.b, a.c);
	}
	else
		fprintf (g,"-1");
	
	fclose(g);
	return 0;
}