Cod sursa(job #779913)

Utilizator NicuCJNicu B. NicuCJ Data 19 august 2012 01:02:28
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
#include <algorithm>
using namespace std;
int a[101];
struct asd
{
	int val;
	int unu;
	int doi;
	int trei;
} sum[1000005];
bool functie(asd A, asd B)
{
	if(A.val<B.val)
		return true;
	return false;
}
int bs(int inc, int sf, int cau)
{
	if(inc>sf)
		return 0;
	int mij=(inc+sf)/2;
	if(sum[mij].val==cau)
	{
		return mij;
	}
	else if(sum[mij].val<cau)
		return bs(mij+1, sf, cau);
	else
		return bs(inc, mij-1, cau);
	return 0;
}
int n, i, s, j, k, v, r[7];
bool ok;
int main()
{
	ifstream f("loto.in");
	ofstream g("loto.out");
	f>>n>>s;
	for(i=1; i<=n; i++)
	{
		f>>a[i];
	}
	sort(a+1, a+n+1);
	for(i=1; i<=n; i++)
	{
		for(j=i; j<=n; j++)
		{
			for(k=j; k<=n; k++)
			{
				v++;
				sum[v].val=a[i]+a[j]+a[k];
				sum[v].unu=a[i];
				sum[v].doi=a[j];
				sum[v].trei=a[k];
			}
		}
	}
	sort(sum+1, sum+v+1, functie);
	for(i=1; i<=v; i++)
	{
		if(bs(1, v, s-sum[i].val))
		{
			ok=true;
			int lb=bs(1, v, s-sum[i].val);
			r[1]=sum[i].unu;r[2]=sum[i].doi;r[3]=sum[i].trei;r[4]=sum[lb].unu;r[5]=sum[lb].doi;r[6]=sum[lb].trei;
			break;
		}
		/*asd kk;
		kk.val=s-sum[i].val;
		if(binary_search(sum+1, sum+v+1, kk.val, functie))
		{
			ok=true;
			int lb=lower_bound(sum+1, sum+v+1, kk.val, functie)-sum;
			r[1]=sum[i].unu;r[2]=sum[i].doi;r[3]=sum[i].trei;r[4]=sum[lb].unu;r[5]=sum[lb].doi;r[6]=sum[lb].trei;
			break;
		}*/
	}
	if(ok)
	{
		sort(r+1, r+7);
		for(i=1; i<=6; i++)
		{
			g<<r[i]<<" ";
		}
	}
	else
		g<<-1;
}