Cod sursa(job #51566)

Utilizator nashnash mit nash Data 14 aprilie 2007 22:03:00
Problema Loto Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

struct nod {
	int s,i,j,k;
};

long i,j,k,n,s,moneda[1001],nr,a,b,mij,ok,util;
nod v[1000001];

class maimic {
	public:
	bool operator() (nod n1,nod n2) {
	return n1.s<n2.s;
	}
};

int main() {
	ifstream fin("loto.in");
	fin>>n>>s;
	for(i=1;i<=n;i++) fin>>moneda[i];
	fin.close();

	ofstream fout("loto.out");

	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			for(k=1;k<=n;k++)
				if(moneda[i]+moneda[j]+moneda[k]<s) {
					v[++nr].s=moneda[i]+moneda[j]+moneda[k];
					v[nr].i=moneda[i];
					v[nr].j=moneda[j];
					v[nr].k=moneda[k];
				}

	sort(v+1,v+nr+1,maimic());

	ok=1;
	for(i=1;i<=nr && ok ;i++)
	{
		util=s-v[i].s;
		ok=1;
		a=1;
		b=nr;
		for(;a<b && ok;) {
			mij=(a+b)/2;
			if(v[mij].s==util) {
				fout<<v[i].i<<" "<<v[i].j<<" "<<v[i].k<<" "<<v[mij].i<<" "<<v[mij].j<<" "<<v[mij].k;
				ok=0;
			}
			if(v[mij].s>util) b=mij-1;
			if(v[mij].s<util) a=mij+1;
		}	
	}

	if(ok) fout<<-1;
	fout.close();

	return 0;
}