Cod sursa(job #629381)

Utilizator giuliastefGiulia Stef giuliastef Data 3 noiembrie 2011 11:22:27
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
// loto - infoarena

#include <fstream>
#include <vector>
#include <algorithm>
#define P 666013
#define NMAX 111
using namespace std;
vector <pair <int, vector<int> > > g[P];
vector <int> sol;
int N,S,x[NMAX];

void read(){
	unsigned int i;
	ifstream f("loto.in");
	f >> N >> S;
	for(i=1;i<=N;i++)
		f >> x[i];
}
int solve(){
	unsigned int i,j,k,ii,sum;
	vector <int> v;
	for(i=1;i<=N;i++)
		for(j=1;j<=N;j++)
			for(k=1;k<=N;k++) {
				sum=x[i]+x[j]+x[k];
				v.push_back(x[i]); 
				v.push_back(x[j]);
				v.push_back(x[k]);
				g[sum%P].push_back(make_pair(sum,v));
				v.clear();
			}
	for(i=0;i<P/2;i++)
		for(j=0;j<g[i].size();j++){
			sum=S-g[i][j].first;
			for(k=0;k<g[sum%P].size();k++)
				if(g[sum%P][k].first==sum){
					for(ii=0;ii<g[i][j].second.size();ii++)
						sol.push_back(g[i][j].second[ii]);
					for(ii=0;ii<g[sum%P][k].second.size();ii++)
						sol.push_back(g[sum%P][k].second[ii]);
					return 1;
				}
		}
	return -1;
}
void write(){
	ofstream g("loto.out");
	if(solve()==1)
		for(vector<int>::iterator it=sol.begin();it!=sol.end(); ++it)
			g<<*it<<" ";
	else
		g<<"-1\n";
}
int main(){
	read();
	write();
	return 0;
}