Cod sursa(job #396257)

Utilizator toniobFMI - Barbalau Antonio toniob Data 14 februarie 2010 20:22:55
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <cstdio>
#include <algorithm>

using namespace std;
const int NMax = 1 << 18;
const int SMax = 1 << 18;

int N, S, v[NMax], s[SMax];

bool comp (int a, int b) {
	return a < b;
}

void afisare (int x) {
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= N; ++j)
			for (int 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);
	
	int i, j, k;
	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)
				s[++s[0]] = v[i] * v[j] * v[k];
	
	sort (s + 1, s + 1 + s[0], comp);
	
	for (i = 1; i <= s[0]; ++i) {
		int lo, hi, mid, x = S - s[i];
		for (lo = 1, hi = v[0]; lo < hi;) {
			mid = lo + (hi - lo) / 2;
			if (s[mid] == x) {
				afisare (s[mid]);
				afisare (x);
				return 0;
			}
			else if (s[mid] < x)
				lo = mid + 1;
			else
				hi = mid - 1;
		}
	}
	printf ("-1\n");
	
	return 0;
}