Cod sursa(job #964388)

Utilizator antonioteoZait Teodor Antonio antonioteo Data 20 iunie 2013 20:15:59
Problema Loto Scor 35
Compilator cpp Status done
Runda becalisme Marime 1.25 kb
#include <cstdio>
#include <algorithm>
#define NMAX 101
using namespace std;

int i, N, S;
int v[NMAX];
int j, k, n;
struct sum{int val, x, y, z;} Sum[NMAX * NMAX * NMAX];
int ind1, ind2;

struct cmp {
	bool operator()(const sum &a, const sum &b) const {
		if (a.val < b.val) return 1;
		return 0;
	}
};

inline int Binary_Search(int cnt) {
	int st = 1, dr = n, mij, x;
	while (st <= dr) {
		mij = (st + dr) / 2;
		x = Sum[mij].val + Sum[cnt].val;
		if (x == S) {
			ind1 = mij; 
			ind2 = cnt; 
			return 1;
		}
		else {
			if (x < S) 
				st = mij + 1;
			else 
				dr = mij - 1;
		}
	}
	return 0;
}

int main() {
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	scanf("%i%i", &N, &S);
	for (i = 1; i <= N; ++i)
		scanf("%i", &v[i]);
	for (i = 1; i <= N; ++i) {
		for (j = 1; j <= N; ++j) {
			for (k = 1; k <= N; ++k) {
				Sum[++n].val = v[i] + v[j] + v[k];
				Sum[n].x = i;
				Sum[n].y = j;
				Sum[n].z = k;
			}
		}
	}
	sort (Sum + 1, Sum + n + 1, cmp());
	for (i = 1; i <= n; ++i) {
		if (Binary_Search(i)) {
			printf("%i %i %i %i %i %i\n", v[Sum[ind1].x], v[Sum[ind1].y], v[Sum[ind1].z], v[Sum[ind2].x], v[Sum[ind2].y], v[Sum[ind2].z]);
			return 0;
		}
	}
	printf("-1\n");
	return 0; 
}