Cod sursa(job #563997)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 26 martie 2011 15:52:42
Problema Loto Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<fstream>
using namespace std;
int a[105],n,s,contor;
struct Suma{int s,x1,x2,x3;};
Suma sum[1000005];

inline bool Ordonare(const Suma A,const Suma B)
{
	return A.s<B.s;
}

int CautareBinara(int x)
{
	int st,dr,m;
	st=0;
	dr=contor-1;
	while(st<=dr)
	{
		m=((st+dr)>>1);
		if(sum[m].s==x)
			return m;
		else
			if(sum[m].s>x)
				dr=m-1;
			else
				st=m+1;
	}
	return -1;
}

int main()
{
	int i,j,k,gasit=0,poz;
	ifstream fin("loto.in");
	fin>>n>>s;
	for(i=0;i<n;i++)
		fin>>a[i];
	fin.close();
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			for(k=0;k<n;k++)
			{
				sum[contor].s=a[i]+a[j]+a[k];
				sum[contor].x1=a[i];
				sum[contor].x2=a[j];
				sum[contor].x3=a[k];
				contor++;
			}
	sort(sum,sum+contor,Ordonare);
	ofstream fout("loto.out");
	for(i=0;i<contor && !gasit;i++)
	{
		poz=CautareBinara(s-sum[i].s);
		if(poz!=-1)
		{
			gasit=1;
			fout<<sum[i].x1<<' '<<sum[i].x2<<' '<<sum[i].x3<<' ';
			fout<<sum[poz].x1<<' '<<sum[poz].x2<<' '<<sum[poz].x3<<"\n";
		}
	}
	if(!gasit)
		fout<<"-1"<<"\n";
	fout.close();
	return 0;
}