Cod sursa(job #51564)

Utilizator nashnash mit nash Data 14 aprilie 2007 21:43:03
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 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();

	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=0;
	for(i=1;i<=nr;i++)
	{
		util=s-v[i].s;
		a=1;
		b=nr;
		for(;a<b;) {
			mij=(a+b)/2;
			if(v[mij].s==util) break;
			if(v[mij].s>util) b=mij-1;
			else a=mij+1;
		}	
		if(v[mij].s=util) {
			ofstream fout("loto.out");
			fout<<v[i].i<<" "<<v[i].j<<" "<<v[i].k<<" "<<v[mij].i<<" "<<v[mij].j<<" "<<v[mij].k;
			fout.close();
			ok=1;
		}
	}

	if(!ok) {
		ofstream fout("loto.out");
		fout<<-1;
		fout.close();
	}
	return 0;
}