Cod sursa(job #346544)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 8 septembrie 2009 16:01:15
Problema Loto Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include<stdio.h>
int i,u,n,j,t,st,dr,ok,m,x,y,z;
long sum,s1,s2,s3,v[101],s[1000005],aux;
int partitionare (int st,int dr)
{
int i,j,m;
int pivot,aux;
m=(st+dr)/2;
pivot=s[m];
i=st-1;
j=dr+1;
while(1)
{
do{++i;}while(s[i]<pivot);
do{--j;}while(s[j]>pivot);
if(i<j)
{
 aux=s[i];
s[i]=s[j];
s[j]=aux;
} //if
else
	return j;
}//while
}//func

void quick(int st,int dr)
{
int p;
if(st<dr)
{
p=partitionare(st,dr);
quick(st,p);
quick(p+1,dr);
}//if
}

int main ()
{
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
  scanf("%d%ld",&n,&sum);
   for(i=1;i<=n;i++)
	scanf("%ld",&v[i]);
for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
	  for(t=1;t<=n;t++)
		 s[++u]=v[i]+v[j]+v[t];
quick(1,u);
for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
	  for(t=1;t<=n;t++)
	  {
		s2=v[i]+v[j]+v[t];s1=sum-s2;
		st=1;
		dr=u;ok=0;
		while(st<=dr)
		{
		   m=(st+dr)/2;
		  if(s1<s[m])
			dr=m-1;
		   else
			  if(s1>s[m])
				 st=m+1;
				 else
					{
					   ok=1;
					   break;
					}

		}
		if(ok)
		   {
			for(x=1;x<=n;x++)
			 for(y=1;y<=n;y++)
			   for(z=1;z<=n;z++)
			   {
				 s3=v[x]+v[y]+v[z];
				 if(s3==s1)
					{
					printf("%ld %ld %ld %ld %ld %ld",v[i],v[j],v[t],v[x],v[y],v[z]);
					 return 0;
					}//if

			   }//for
		   }//if ok
	   } //for
if(ok==0)
  printf("-1");
	return 0;
}