Cod sursa(job #317577)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 24 mai 2009 00:00:13
Problema Loto Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <stdio.h>
#define N 1000001
int m[N],nr[101];
void quick(int st,int dr)
{int s=st,d=dr,p=m[s+rand()%(dr-st+1)],aux;
 while(s<d)
 {while(m[s]<p)s++;
  while(m[d]>p)d--;
  if(s<=d)
  {aux=m[s];
   m[s]=m[d];
   m[d]=aux;
   s++;
   d--;
  }
 }
 if(s<dr)quick(s,dr);
 if(st<d)quick(st,d);
}
int main ()
{freopen("loto.in","r",stdin);
 freopen("loto.out","w",stdout);
 int n,i,j,k,l,s,a1,a2,flag;
 scanf("%d %d",&n,&s);
 for (i=1;i<=n;i++)
 {scanf("%d",&nr[i]);
 }
 for (i=1,l=1;i<=n;i++)
 {for (j=i;j<=n;j++)
  {for (k=j;k<=n;k++)
   {m[l++]=nr[i]+nr[j]+nr[k];
   }
  }
 }
 quick(1,l-1);
 for (i=2,j=1;i<l;i++)
 {if(m[i]!=m[j])
  {m[++j]=m[i];
  }
 }
 i=1;
 flag=0;
 while(i<=j)
 {if(m[i]+m[j]>s)
  {while(m[i]+m[j]>s)j--;
  }
  else
  {while(m[i]+m[j]<s)i++;
  }
  if(m[i]+m[j]==s)
  {flag=1;
   a1=m[i];
   a2=m[j];
   break;
  }
 }
 if(flag==0)
 {printf("-1");
 }
 else
 {for (i=1;i<=n;i++)
  {for (j=i;j<=n;j++)
   {for (k=j;k<=n;k++)
    {if(nr[i]+nr[j]+nr[k]==a1)
     {printf("%d %d %d ",nr[i],nr[j],nr[k]);
      break;
     }
    }
    if(nr[i]+nr[j]+nr[k]==a1)break;
   }
   if(nr[i]+nr[j]+nr[k]==a1)break;
  }
  for (i=1;i<=n;i++)
  {for (j=i;j<=n;j++)
   {for (k=j;k<=n;k++)
    {if(nr[i]+nr[j]+nr[k]==a2)
     {printf("%d %d %d",nr[i],nr[j],nr[k]);
      break;
     }
    }
    if(nr[i]+nr[j]+nr[k]==a2)break;
   }
   if(nr[i]+nr[j]+nr[k]==a2)break;
  }
 }
 return 0;
}