Cod sursa(job #227284)

Utilizator c_e_manuEmanuel Cinca c_e_manu Data 3 decembrie 2008 23:51:39
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<fstream.h>

ifstream fin("loto.in");
ofstream fout("loto.out");
int a[101],k,i,n,s,sum[101],j,l=1,ok,mid,st,dr;
struct poz{int x,y,z;};
poz p[101];
void divide(int s, int d, int&m)
{	int i=s,j=d,pi=0,pj=1;
	while(i<j)
	{	if(sum[i]>sum[j])
			sum[i]^=sum[j]^=sum[i]^=sum[j],pi^=pj^=pi^=pj,
			p[i].x^=p[j].x^=p[i].x^=p[j].x,
			p[i].y^=p[j].y^=p[i].y^=p[j].y,
			p[i].z^=p[j].z^=p[i].z^=p[j].z;
		i+=pi;j-=pj;
	}
	m=i;
}
void qsort(int s, int d)
{       int m;
	if(s<d)
	{	divide(s,d,m);
		qsort(s,m-1);
		qsort(m+1,d);
	}
}
int main()
{       fin>>n>>s;
	for(i=1;i<=n;i++)
		fin>>a[i];
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			for(k=1;k<=n;k++)
			{	sum[l]=a[i]+a[j]+a[k];
				p[l].x=i;p[l].y=j;p[l++].z=k;
			}
	qsort(1,l-1);
	for(i=1;i<=l&&!ok;i++)
	{	st=1,dr=l;
		while(st<=dr&&!ok)
		{       mid=(st+dr)/2;
			if(sum[i]+sum[mid]==s)
			{	fout<<a[p[i].x]<<' '<<a[p[i].y]<<' '<<a[p[i].z]<<' '<<a[p[mid].x]<<' '<<a[p[mid].y]<<' '<<a[p[mid].z];
				ok=1;
			}
			else	if(sum[i]+sum[mid]>s)
					dr=mid-1;
				else
					st=mid+1;
		}
	}
	if(!ok) fout<<"-1";
	return 0;
}