Cod sursa(job #496985)

Utilizator andunhillMacarescu Sebastian andunhill Data 31 octombrie 2010 20:15:11
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("loto.in");
ofstream g("loto.out");
int N;
struct suma
{	int val,x,y,z;
}v[101*101*101];
bool cmp(suma a,suma b)
{	return ( a.val<b.val );
}

int main()
{	int S,i,j,k,xx,vall,mid,left,right;
	bool ok;
	int a[101];
	f>>N>>S;
	for(i=1;i<=N;i++)
		f>>a[i];
	xx=1;
	for(i=1;i<=N;i++)
		for(j=i;j<=N;j++)
			for(k=j;k<=N;k++)
				v[xx].val=a[i]+a[j]+a[k] , v[xx].x=a[i] , v[xx].y=a[j] , v[xx].z=a[k] , xx++;
	xx--;
	sort(v+1,v+xx+1,cmp);
	for(i=1;i<=N;i++)
	{	left=1, right=xx;
		vall=S-v[i].val;
		ok=0;
		while(left<=right)
		{	mid=(left+right)/2;
			if(vall==v[mid].val)
			{	j=mid; ok=1; break; }
			if(vall<v[mid].val) right=mid-1;
			else left=mid+1;
		}
		if(ok)
		{	g<<v[i].x<<" "<<v[i].y<<" "<<v[i].z<<" "<<v[j].x<<" "<<v[j].y<<" "<<v[j].z; break; }
	}
	if(!ok)
		g<<-1;
	f.close();
	g.close();
	return 0;
}