Cod sursa(job #2532)

Utilizator alle_forever13Alexandra Retegan alle_forever13 Data 17 decembrie 2006 17:41:30
Problema Loto Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include<stdio.h>

#include<stdlib.h>

#define input "loto.in"

#define output "loto.out"

#define dim 101

struct triplu
{

	long x, y, z, s;

};

long x[dim], n, s, l;

triplu a[dim*dim*dim];

FILE *in, *out;

void citire();
void tipar(long i, long j);
void rezolva();
void qsort(long p, long q);
long divide(long p, long q);
long cbin(long ls, long ld, long k);

int main()
{
	in = fopen (input, "r");

	out = fopen (output, "w");

	citire();

	rezolva();

	return 0;

}

void citire()
{
	fscanf(in, "%ld%ld", &n, &s);

	for(int i=1; i<=n; ++i)

		fscanf(in, "%ld", &x[i]);

}

void tipar(long i, long j)
{
	fprintf(out, "%ld %ld %ld %ld %ld %ld", a[i].x, a[i].y, a[i].z, a[j].x, a[j].y, a[j].z);

	exit(0);

}

 void rezolva()
{
	long i, j, k;

	for(i=1; i<=n; ++i)

		for(j=1; j<=n; ++j)

			for(k=1; k<=n; ++k)
			{
				++l;

				a[l].x = x[i];

				a[l].y = x[j];

				a[l].z = x[k];

				a[l].s = x[i]+x[j]+x[k];
			}

	qsort(1, l);

	for(i=1; i<=l; ++i)
	{
		j = cbin (1, l, s-a[i].s);

		if(j)

			tipar(i, j);

	}

	fprintf(out, "-1");

}

void qsort(long p, long q)
{
	long m=divide(p, q);

	if(m-1 > p)

		qsort(p, m-1);

	if(m+1 < q)

		qsort(m+1, q);

}

long divide(long p, long q)
{
	long st = p, dr = q;

	triplu x = a[p];

	while(st<dr)
	{
		while(st<dr && a[dr].s>=x.s)

			-- dr ;

		a[st]=a[dr];

		while(st<dr && a[st].s<=x.s)

			++ st ;

		a[dr]=a[st];


	}

	a[st]=x;

	return st;

}

long cbin(long ls, long ld, long k)
{
	int m;

	while(ls<=ld)
	{
		m= (ls+ld)>>1;

		if(a[m].s==k)

			return m;

		if(a[m].s<k)

			ls = m+1;

		else

			ld = m-1;

	}

	return 0;

}