Cod sursa(job #14173)

Utilizator peanutzAndrei Homorodean peanutz Data 8 februarie 2007 13:38:41
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <stdio.h>
#include <stdlib.h>

#define SMAX 1000010
#define NMAX 110

typedef struct form
{
long x, y, z;
};
form format[SMAX];

long a[NMAX], sume[SMAX];
long s, n;
long nr;


void read()
{
long i;

scanf("%ld %ld\n", &n, &s);

for(i = 0; i < n; ++i)
	scanf("%ld\n", &a[i]);
}


void fa_sume()
{
long for1, for2, for3;


for(for1 = 0; for1 < n; ++for1)
	for(for2 = 0; for2 < n; ++for2)
		for(for3 = 0; for3 < n; ++for3)
			{
				sume[nr] = a[for1] + a[for2] + a[for3];

				format[nr].x = a[for1];
				format[nr].y = a[for2];
				format[nr++].z = a[for3];

			}
}

long divide(long p, long q)
{
long st = p, dr = q, x = sume[p];
form xf = format[p];

while(st < dr)
	{
		while(st < dr  &&  x <= sume[dr]) --dr;
		sume[st] = sume[dr];
		format[st] = format[dr];

		while(st < dr  &&  x >= sume[st]) ++st;
		sume[dr] = sume[st];
		format[dr] = format[st];
	}
a[st] = x;
format[st] = xf;

return st;
}


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);

}


void abort_it(long a, long b)
{
printf("%ld %ld %ld ", format[a].x, format[a].y, format[a].z);

printf("%ld %ld %ld\n", format[b].x, format[b].y, format[b].z);


fclose(stdin);
fclose(stdout);

exit(0);
}


void find()
{
long i, st, dr, m, search;


for(i = 0; i < nr; ++i)
	{
		search = s - sume[i];

		st = 0;
		dr = nr-1;

		while(st <= dr)
			{
				m = (st+dr)/2;

				if(sume[m] == search)
					abort_it(i, m);

				else if(search > sume[m])
					st = m+1;

				else
					dr = m-1;

			}
	}
}


int main()
{
freopen("loto.in", "r", stdin);
freopen("loto.out", "w", stdout);

read();

fa_sume();

qsort(0, nr-1);

find();

printf("-1\n");

fclose(stdin);
fclose(stdout);

return 0;
}