Cod sursa(job #2354830)

Utilizator skoda888Alexandru Robert skoda888 Data 25 februarie 2019 16:57:55
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb

#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

struct cls {
	long suma;
	int i1, i2, i3;
	bool operator< (const cls& x) const {
		return suma < x.suma;
	}
};

vector< long > v;
int N;
long S;

void cit() {
	ifstream f("loto.in");
	int x;

	f >> N >> S;
	for (int i = 0; i < N; i++) {
		f >> x;
		v.push_back(x);
	}
}

int bs(const vector<cls>& a, const long& val) {
	int i, step, n = a.size();

	for (step = 1; step < n; step <<= 1);

	for (step >>= 1, i = n - 1; a[i].suma != val && step; step >>= 1)
		if (i - step >= 0)
			if (a[i - step].suma >= val)
				i -= step;
	if (a[i].suma == val)
		return i;
	else
		return -1;
}

void rez() {
	cls x;
	vector< cls > a;
	int i, j, k, poz;

	for (i = 0; i < N; i++)
		for (j = i; j < N; j++)
			for (k = j; k < N; k++) {
				x.suma = v[i] + v[j] + v[k];
				x.i1 = i; x.i2 = j; x.i3 = k;
				a.push_back(x);
			}
	sort(a.begin(), a.end());

	ofstream g("loto.out");
	for (i = 0; i < N; i++)
		for (j = i; j < N; j++)
			for (k = j; k < N; k++) {
				poz = bs(a, S - v[i] - v[j] - v[k]);
				if (poz != -1) {
					x = a[poz];
					g << v[i] << " " << v[j] << " " << v[k] << " " << v[x.i1] << " " << v[x.i2] << " " << v[x.i3] << endl;
					return;
				}
			}
	g << "-1" << endl;
}

int main() {
	cit();
	rez();
	return 0;
}