Cod sursa(job #178588)

Utilizator me_andyAvramescu Andrei me_andy Data 14 aprilie 2008 19:50:02
Problema Loto Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<fstream.h>
#include<stdlib.h>

 ifstream f("loto.in");
 ofstream g("loto.out");
 int s[1000006],a[102],x,y,n,i,j,k,ok;

int sort(const void*a,const void*b)
{
 return (*((int*)a)-*((int*)b));
}
void afisare(int ab)
{
 for(int i=1;i<=x;i++)
  for(int j=1;j<=x;j++)
   for(int k=1;k<=x;k++)
    if(a[i]+a[j]+a[k]==ab)
    {
     g<<a[i]<<" "<<a[j]<<" "<<a[k]<<" ";
     return;
    }
}
int cb(int sum)
{
 int st=1,dr=n,m;
 while(st<=dr)
 {
  m=(st+dr)/2;
  if(sum<s[m]) dr=m-1;
  if(s[m]<sum) st=m+1;
  if(s[m]==sum)
  return m+1;
 }
 return 0;
}
int main()
{
 f>>x;
 f>>y;
 for(i=1;i<=x;i++)
  f>>a[i];
 n=0;
 for(k=1;k<=x;k++)
  for(i=1;i<=x;i++)
   for(j=1;j<=x;j++)
   {
    n++;
    s[n]=a[k]+a[i]+a[j];
   }
 qsort(&s[1],n,sizeof(int),sort);
 ok=0;
 for(i=1;i<=n;i++)
 {
  if(s[i]<y)
  {
   if(cb(y-s[i]))
   {
    afisare(s[i]);
    afisare(y-s[i]);
    ok=1;
    break;
   }

 } else break;
 }
 if(ok==0)
  g<<-1;
 f.close();
 g.close();
 return 0;
}