Cod sursa(job #172450)

Utilizator plastikDan George Filimon plastik Data 6 aprilie 2008 14:11:17
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <cstdio>
#include <vector>
#include <set>
#include <map>
using namespace std;

map<int, multiset<int> > Sums;
map<int, multiset<int> >::iterator it;
multiset<int> Sol;

multiset<int>::iterator msi;
set<int>::iterator si;
vector<int> Have;
int n, des;

int main() {
	
	freopen("loto.in", "r", stdin);
	
	scanf("%d %d", &n, &des);
	int i, tmp;
	for (i = 0; i < n; ++ i) {
		scanf("%d", &tmp);
		Have.push_back(tmp);
	}
	
	int j, k;
	multiset<int> Tmp;
	for (i = 0; i < n; ++ i)
		for (j = 0; j < n; ++ j)
			for (k = 0; k < n; ++ k) {
				Tmp.clear();
				Tmp.insert(i);
				Tmp.insert(j);
				Tmp.insert(k);
				
				Sums.insert(make_pair(Have[i] + Have[j] + Have[k], Tmp));
			}
	int csum;
	bool found = false;
	for (i = 0; i < n; ++ i)
		for (j = 0; j < n; ++ j)
			for (k = 0; k < n; ++ k) {
				csum = des - Have[i] - Have[j] - Have[k];
				if (csum <= 0)
					continue;
				
				it = Sums.find(csum);
				if (it != Sums.end()) {
					
					Sol.insert(Have[i]), Sol.insert(Have[j]), Sol.insert(Have[k]);
					for (si = it->second.begin(); si != it->second.end(); ++ si)
						Sol.insert(Have[*si]);
					found = true;
					goto end;
				}
			}
		
end:
	if (found == true) {
		for (msi = Sol.begin(); msi != Sol.end(); ++ msi)
			printf("%d ", *msi);
	} else
		printf("-1");
	
	return 0;
}