Cod sursa(job #907552)

Utilizator vld7Campeanu Vlad vld7 Data 8 martie 2013 00:52:30
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>
#include <algorithm>

using namespace std;

FILE *f = fopen ("loto.in","r");
FILE *g = fopen ("loto.out","w");

const int MAX_N = 105;

struct sm {
	int val, t[3];
};

int n, S, a[MAX_N], cnt;
sm sum[MAX_N * MAX_N * MAX_N];

bool cmp(const sm i, const sm j) {
	return i.val < j.val;
}

void read() {
	fscanf (f, "%d %d", &n, &S);
	for (int i = 1; i <= n; i++)
		fscanf (f, "%d", &a[i]);
}

int binsearch(int V) {
	int lo = 1, hi = cnt, mid;
	
	while (lo <= hi) {
		mid = lo + (hi - lo) / 2;
		if (sum[mid].val == V)
			return mid;
		else if (sum[mid].val > V)
			hi = mid - 1;
		else
			lo = mid + 1;
	}
	
	return -1;
}

void precompute() {
	for (int i = 1; i <= n; i++)
		for (int j = i; j <= n; j++)
			for (int k = j; k <= n; k++) 
				if (a[i] + a[j] + a[k] <= S) {
					cnt++;
					sum[cnt].val = a[i] + a[j] + a[k];
					sum[cnt].t[0] = a[i];
					sum[cnt].t[1] = a[j];
					sum[cnt].t[2] = a[k];
				}
	sort (sum + 1, sum + cnt + 1, cmp);
}

void solve() {
	int ok = 0;
	for (int i = 1; i <= cnt && !ok; i++) {
		int poz = binsearch(S - sum[i].val);
		if (poz != -1) {
			int x[3], y[3];
			ok = 1;
			
			for (int j = 0; j <= 2; j++) {
				x[j] = sum[i].t[j];
				y[j] = sum[poz].t[j];
			}
			for (int j = 0; j <= 2; j++)
				fprintf (g, "%d %d ", x[j], y[j]);
		}
	}
	
	if (!ok)
		fprintf (g, "-1\n");
}

int main() {
	read();
	precompute();
	solve();
	
	fclose(f);
	fclose(g);
	
	return 0;
}