Cod sursa(job #121431)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 8 ianuarie 2008 18:46:04
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include<stdio.h>
int n,p,i,j,k,s,max,min,y,ok1,ok2,b,c,d,a[101],v[101],f[601],sume[1001];

void merge(int st, int dr)
{
int ok,g,m,i,j,k;
if(st<dr)
	{
	m=(st+dr)/2;
	merge(st,m);
	merge(m+1,dr);
	//interclasare  st-->m       m+1-->dr
	i=st;
	j=m+1;
	ok=1;
	k=0;
	while(ok)
		{
		if(sume[i]<sume[j])
			a[++k]=sume[i++];
		else
			a[++k]=sume[j++];
		if (i>m || j>dr)
			ok=0;
		}
	for(g=j;g<=dr;g++)
		a[++k]=sume[g];
	for(g=i;g<=m;g++)
		a[++k]=sume[g];
	k=0;
	for(i=st;i<=dr;i++)
		sume[i]=a[++k];
	}
}

int bs(int st, int dr)
{
int m,sp;
m=(st+dr)>>1;
sp=p-sume[i];
if(st>dr)
  return -1;
if(sp==sume[m])
  return m;
if(sp<sume[m])
  return bs(st,m-1);
return bs(m+1,dr);
}

int main()
{
freopen("loto.in","r",stdin);
freopen("loto.out","w",stdout);
scanf("%d%d",&n,&p);
for(i=1;i<=n;i++)
  {
  scanf("%d",&v[i]);
  if(v[i]>max)
    max=v[i];
  if(v[i]<min)
    min=v[i];
  }
if(p>6*max || p<6*min)
  {
  printf("-1");
  return 0;
  }
for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
    for(k=1;k<=n;k++)
      {
      s=v[i]+v[j]+v[k];
      if(f[s]==0)
	{
	++f[s];
	sume[++y]=s; //y=pozitia sumei v[i]+v[j]+v[k] in vect sume[]
	}
      }
merge(1,y);
for(i=1;i<=y;i++)
  {
  j=bs(i,y);
  if(j!=-1)
    for(b=1;b<=n;b++)
      for(c=1;c<=n;c++)
	for(d=1;d<=n;d++)
	  {
	  s=v[b]+v[c]+v[d];
	  if(s==sume[i] && ok1==0)
	    {
	    printf("%d %d %d ",v[b],v[c],v[d]);
	    ok1=1;
	    }
	  if(s==sume[j] && ok2==0)
	    {
	    printf("%d %d %d ",v[b],v[c],v[d]);
	    ok2=1;
	    }
	  if(ok1 && ok2)
	    return 0;
	  }
  }
printf("-1");
return 0;
}