Cod sursa(job #1141070)

Utilizator alexandru70Ungurianu Alexandru alexandru70 Data 12 martie 2014 16:14:57
Problema Loto Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

struct Sum {
	size_t i1,i2,i3;
	unsigned s;
	Sum() {}
	Sum(unsigned _s,size_t _i1, size_t _i2, size_t _i3) {
		s = _s;
		i1 = _i1;
		i2 = _i2;
		i3 = _i3;
	}
	bool operator<(const Sum &a) const {
		return s < a.s;
	}
};


int main() {
	ifstream in("loto.in");
	size_t n;
	unsigned s;
	in >> n >> s;
	vector<unsigned> v(n);
	for(size_t i = 0; i < n; ++i) {
		in >> v[i];
	}

	vector<Sum> sums;

	for(size_t i = 0; i < n; ++i)
		for(size_t j = 0; j < n; ++j)
			for(size_t k = 0; k < n; ++k)
				sums.push_back(Sum(v[i]+v[j]+v[k],i,j,k));

	sort(sums.begin(), sums.end());

	ofstream out("loto.out");

	bool hasSol = false;

	for(size_t i = 0; i < sums.size(); ++i) {
		int remS = s-sums[i].s;
		auto it = upper_bound(sums.begin(), sums.end(),Sum(remS,0,0,0)) - 1;
		if(it->s == remS) {
			out << v[sums[i].i1] << ' ' << v[sums[i].i2] << ' ' << v[sums[i].i3] << ' ';
            out << v[it->i1] << ' ' << v[it->i2] << ' ' << v[it->i3] << '\n';
            hasSol = true;
            break;
		}
	}
	if(!hasSol) out << -1 << '\n';

	return 0;
}