Cod sursa(job #451024)

Utilizator miculprogramatorA Cosmina - vechi miculprogramator Data 8 mai 2010 20:58:48
Problema Loto Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <stdio.h>

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

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

int main ()
{
	FILE *f = fopen ("loto.in","r");
	FILE *g = fopen ("loto.out","w");
	fscanf (f,"%ld %lld", &n, &S);
	for (i=1; i<=n; ++i)
		fscanf (f,"%ld", &nr[i]);
	fclose(f);
	
	for (i=1; i<=n; ++i)
		for (j=1; j<=n; ++j)
			for (k=1; 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);
	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,"%d %d %d %d %d %d", b.a, b.b, b.c, a.a, a.b, a.c);
	}
	else
		fprintf (g,"-1");
	
	fclose(g);
	return 0;
}