Cod sursa(job #555816)

Utilizator tinkyAndrei Ilisei tinky Data 15 martie 2011 19:44:46
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<fstream>
#define forn(i,n) for (i=1;i<=n;i++)
using namespace std;
int n,s,nn;
int a[100],v[1000002];
void citire()
{
	int i;
	ifstream in("loto.in");
	in>>n>>s;
	for (i=1;i<=n;i++)
		in>>a[i];
}

int binar(int x)
{
	int inc=1,sf=nn,mij;
	while (sf!=inc)
	{
		mij=(inc+sf)/2;
		if (x>v[mij])
			inc=mij+1;
		else if (x<v[mij])
			sf=mij-1;
		else if (v[mij]==x)
			return mij;
	}
	return -1;
}
	
int main()
{
	int i,j,k,l,c=0,b=0,ok1=1,ok2=2;
	ofstream out("loto.out");
	citire();
	l=1;
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			for (k=1;k<=n;k++)
			{
				v[l]=a[i]+a[j]+a[k];
				l++;
			}	
	nn=n*n*n;
	sort(v+1,v+nn+1);
	for (i=1;i<=nn;i++)
		if (binar(s-v[i])!=-1)
		{
			c=s-v[i];
			b=v[i];
		}
	if (!c&&!b)
	{
		out<<-1;
		return 0;
	}
	for (i=1;i<=n&&(ok1||ok2);i++)
		for (j=1;j<=n&&(ok1||ok2);j++)
			for (k=1;k<=n&&(ok1||ok2);k++)
			{
				if (a[i]+a[j]+a[k]==c&&ok1)
				{
					out<<a[i]<<" "<<a[j]<<" "<<a[k]<<" ";
					ok1=0;
				}
				if (a[i]+a[j]+a[k]==b&&ok2)
				{
					out<<a[i]<<" "<<a[j]<<" "<<a[k]<<'\n';
					ok2=0;
				}
			}
	
}