Cod sursa(job #5088)

Utilizator dzsDonca Zsolt dzs Data 10 ianuarie 2007 00:59:54
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
// Loto.cpp : Defines the entry point for the console application.
//

#include <stdio.h>
//#include <conio.h>

#pragma warning(disable : 4996)

long n, s;
long v[100];
long sz[6] = {0};

typedef struct{
	long a, pi, pj, pk;
} XAR;

XAR q[100*100*100];
long qlen;

int sortq(long lo, long hi)
{
	long i = lo, j = hi, x = q[(lo + hi) / 2].a;
	XAR y;
	do{
		while (q[i].a < x) i++;
		while (x < q[j].a) j--;
		if (i <= j)
		{
			y = q[i];
			q[i] = q[j];
			q[j] = y;
			i++;
			j--;
		}
	}while (!(i > j));
	if (lo < j) sortq(lo, j);
	if (i < hi) sortq(i, hi);
	return 0;
}

long searchq(long num, long lo, long hi)
{
	long rv, m, x;
	if (num < q[lo].a || num > q[hi].a)
	{
		rv = -1;
	} else
	{
		m = (lo+hi)/2;
		x = q[m].a;
		if (lo == hi)
		{
			if (num == x)
			{
				rv = m;
			} else {
				rv = -1;
			}
		} else {
			if (x > num)
			{
				rv = searchq(num, lo, m-1);
			} else {
				rv = searchq(num, m+1, hi);
			}
		}
	}
	return rv;
}

int main(int argc, char* argv[])
{
	long i, j, k;
	FILE *f = fopen("loto.in","r");
	fscanf(f, "%ld %ld", &n, &s);
	for(i=0;i<n;i++) fscanf(f, "%ld", &v[i]);
	fclose(f);

	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			for(k=0;k<n;k++)
			{
				long index = (i*n*n)+(j*n)+k;
				q[index].a = v[i] + v[j] + v[k];
				q[index].pi = i;
				q[index].pj = j;
				q[index].pk = k;
			}
	qlen = (n-1)*(n*n + n + 1);
	sortq(0, qlen);

	bool found = false;

	for(i=0;i<=qlen;i++)
	{
		k = s-q[i].a;
		if (k > 0)
		{
			j = searchq(k, 0, qlen);
			if (j != -1)
			{
				found = true;
				break;
			}
		}
	}
	f = fopen("loto.out","w");
	if (found)
	{
		fprintf(f, "%ld %ld %ld %ld %ld %ld", v[q[i].pi], v[q[i].pj], v[q[i].pk], v[q[j].pi], v[q[j].pj], v[q[j].pk]);
	} else {
		fprintf(f, "-1");
	}

	fclose(f);
	return 0;
}