Cod sursa(job #575791)

Utilizator andrei.finaruFinaru Andrei Emanuel andrei.finaru Data 8 aprilie 2011 18:59:03
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<fstream.h>
#include<algorithm>
ifstream f("loto.in");
ofstream g("loto.out");
struct form{int a,b,c,z;} v1[1000005];
int n,q,s[105],ii,jj,ok,st,dr,mij,tz,nr,w,sol[8];
//int v[1000005];
int cauta(int a, int &jj)
{
	st=1; dr=nr;
	while(st<=dr)
		{ mij=(st+dr)/2;
		  if(v1[mij].z==a) {jj=mij;return 1;}
		  if(v1[mij].z<a) st=mij+1;
			  else dr=mij-1;
		}
	return 0;
}

int cmp(form a, form b)
{ return (a.z<b.z); }

int main()
{
	int i,j,k;
	f>>n>>q;
	for(i=1;i<=n;++i) f>>s[i];
	//std::sort(s+1,s+n+1);
	for(i=1;i<=n;++i)
		for(j=i;j<=n;++j)
			for(k=j;k<=n;++k)
				{ v1[++nr].z=s[i]+s[j]+s[k];
				  v1[nr].a=s[i];
				  v1[nr].b=s[j];
				  v1[nr].c=s[k];
				}
	std::sort(v1+1,v1+nr+1,cmp);
	/*w=1;
	while(v[w]+v[nr]<q) ++w;
	tz=nr;
	while(2*v[tz]>q) --tz;
	++tz;*/
	for(i=1;i<=n&&!ok;++i)
		if(cauta(q-v1[i].z,jj)) ok=1,ii=i;
	if(ok) 
		{ sol[0]=v1[ii].a;
		  sol[1]=v1[ii].b;
		  sol[2]=v1[ii].c;
		  sol[3]=v1[jj].a;
		  sol[4]=v1[jj].b;
		  sol[5]=v1[jj].c;
		  std::sort(sol+1,sol+6);
		  for(i=0;i<6;++i) g<<sol[i]<<' ';
		  g<<'\n';
		}
		else g<<-1<<'\n';
	f.close(); g.close();
	return 0;
}