Cod sursa(job #164976)

Utilizator coderninuHasna Robert coderninu Data 25 martie 2008 00:14:39
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <stdio.h>
#define Nmax 101

int v[Nmax], c[Nmax * Nmax * Nmax];
int i, j, k, n, s, nr;


inline void swap(int &x, int &y) { int temp = x; x = y; y = temp; }

void sort(int p, int q)
{
	int st = p, dr = q, m = c[(p+q)/2];
	while (st < dr)
	{
		while (c[st] < m) st++;
		while (c[dr] > m) dr--;
		if (st <= dr) swap(c[st++],c[dr--]);
	}
	if (p < dr) sort(p,dr);
	if (st < q) sort(st,q);
}



void write(int x)
{
	for (i=1; i<=n; i++)
		for (j = 1; j<=n; j++)
			for (k = 1; k<=n; k++)
				if (v[i] + v[j] + v[k] == x)
				{
					printf("%d %d %d ", v[i], v[j], v[k]);
					return;
				}
}

int main()
{
	freopen("loto.in", "r", stdin);
	freopen("loto.out", "w", stdout);
	scanf("%d %d\n", &n, &s);
	for (i=1; i<=n; i++) scanf("%d ", v+i);
	for (i=1; i<=n; i++)
		for (j=1; j<=n; j++)
			for (k=1; k<=n; k++)
				c[++nr] = v[i] + v[j] + v[k];
	sort(1,nr);
	for (int st = 1, dr = nr; st <=dr; )
	{
		for (; c[st] + c[dr] > s && st < dr; dr--);
		if (c[st] + c[dr] == s) 
		{
			write(c[st]);
			write(c[dr]);
			return 0;
		}
		if (st == dr) break;
		for (; c[st] + c[dr] < s && st < dr; st++);
	}
	printf("-1");
	return 0;
}