Cod sursa(job #1142673)

Utilizator dec0o0dinu pinu dec0o0 Data 14 martie 2014 01:19:51
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int n, s;
vector<vector<int> > v;
vector<int> val;
int cauta_binar(int inc, int fin, int valoare);
bool sorteaza(vector<int> a, vector<int> b) {
	return a[0] >= b[0];
}

int main(){
	ifstream f("loto.in");
	ofstream g("loto.out");

	f>>n;
	f>>s;
	val = vector<int> (n);
	//cerr << n << ' ' << s << ' ';
	for (int i=0; i<n; i++) {
		f>>val[i];
	}

	v = vector<vector<int> > ();
	vector<int> aux = vector<int>(4,0);

	for (int i=0; i<n; i++)
		for (int j=0; j<n; j++)
			for (int k=0; k<n; k++) {
				aux[0] = val[i]+val[j]+val[k];
				aux[1] = val[i];
				aux[2] = val[j];
				aux[3] = val[k];
				v.push_back(aux);
			}

	sort(v.begin(), v.end(), sorteaza);

	bool gasit = false;
	int i=0, sol=-1;
	int nn = v.size();

	for (i=0; i<nn/2 && !gasit; i++) {
		sol = cauta_binar(i, nn, s-v[i][0]);
		if (sol != -1) gasit = true;
	}

	if (!gasit)
		g<<"-1";
	else {
		//cerr <<v[i-1][0]<< ' ' << v[sol][0];
		for (int j=1; j<4;j++)
			g<<v[i-1][j]<<' '<<v[sol][j]<<' ';
	}

	f.close();
	g.close();
	return 0;
}

int cauta_binar(int inc, int fin, int valoare) {
	int index;
	//cerr<< inc << ' ' << fin << ' ' << valoare << endl;
	if (inc >= fin)
		index = -1;
	else {
		int m = (inc + fin)/2;
		if (v[m][0] == valoare)
			index = m;
		else
			if (valoare < v[m][0])
				index = cauta_binar(inc, m-1, valoare);
			else
				index = cauta_binar(m+1, fin, valoare);
	}
	return index;
}