Cod sursa(job #396303)

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

using namespace std;
const int NMax = 1 << 7;
const int AMax = 1 << 20;

int N, S, v[NMax], a[AMax];

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;
				}
			}
		}
	}
}
/*
void afisare (int q) {
	int i, j, k;
	i = q / (N * N);
	if (q % (N * N)) i++;
	q = q % (N * N);
	j = q / N;
	if (q % N) j++;
	q = q % N;
	k = q;
	if (q == 0) k = 1;
	printf ("%d %d %d ", v[i], v[j], v[k]);
}
*/
int BS (int m) {
	int i, step;
	for (step = 1; step < v[0]; step <<= 1) {}
	for (i = 0; step; step >>= 1) {
		if (i + step <= v[0] && a[i + step] <= S - a[m]) {
			i += step;
		}
	}
	
	if (a[i] == S - a[m]) { 
		afisare(i);
		afisare(m);
		return 1;
	}
	return -1;
}

int main () {
	freopen ("loto.in", "r", stdin);
	freopen ("loto.out", "w", stdout);
	
	scanf ("%d %d", &N, &S);
	for (int i = 1; i <= N; ++i) {
		scanf ("%d", &v[i]);
	}
	
	sort (v + 1, v + 1 + N, comp);
	
	for (int i = 1; i <= N; ++i) { 
		for (int j = i; j <= N; ++j) {
			for (int k = i; k <= N; ++k) {
				a[++v[0]] = v[i] + v[j] + v[k];
			}
		}
	}
	
	for (int m = 1; m <= v[0]; ++m) {
		if (BS (m) == 1) {
			return 0;
		}
	}
	printf ("-1\n");
	
	return 0;
}