Cod sursa(job #107506)

Utilizator me_andyAvramescu Andrei me_andy Data 19 noiembrie 2007 21:55:36
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include<fstream.h>
#define max 1000000

 ifstream f("loto.in");
 ofstream g("loto.out");
 long s[max],s1[max],s2[max],s3[max],n,m,x[102],cont,y,po[10];
 int i,j,l,p,ok ;

int calcul(int st,int dr,int suma)
{
 int mij;
 mij=(st+dr)/2;
 if(mij==st&& mij==dr && s[mij]!=suma)
  return 0;
 if(s[mij]==suma)
  return mij;
 else
 {
  if(suma<s[mij])
   calcul(st,mij-1,suma);
  else
   calcul(mij+1,dr,suma);
 }
}
void imparte (int st,int dr,int &p)
{
 int i,j,ii,jj,aux;
 i=st;
 j=dr;
 ii=0;
 jj=-1;
 while(i<j)
 {
  if(s[i]>s[j])
  {
   aux=s[i];
   s[i]=s[j];
   s[j]=aux;
   aux=ii;
   ii=-jj;
   jj=-aux;
   }
 i=i+ii;
 j=j+jj;
 }
 p=i;
}
void qsort(int st,int dr)
{
 if(st<dr)
 {
  imparte(st,dr,p);
  qsort(st,p-1);
  qsort(p+1,dr);
 }
}


void imparte2 (int st,int dr,int &p)
{
 int i,j,ii,jj,aux;
 i=st;
 j=dr;
 ii=0;
 jj=-1;
 while(i<j)
 {
  if(po[i]>po[j])
  {
   aux=po[i];
   po[i]=po[j];
   po[j]=aux;
   aux=ii;
   ii=-jj;
   jj=-aux;
   }
 i=i+ii;
 j=j+jj;
 }
 p=i;
}
void qsort2(int st,int dr)
{
 if(st<dr)
 {
  imparte2(st,dr,p);
  qsort(st,p-1);
  qsort(p+1,dr);
 }
}
int main()
{

 f>>n;
 f>>m;
 for(i=1;i<=n;i++)
 f>>x[i];
 cont=1;
 for(i=1;i<=n;i++)
  for(j=i;j<=n;j++)
   for(l=j;l<=n;l++)
    {
     s[cont]=x[i]+x[j]+x[l];
     s1[cont]=x[i];
     s2[cont]=x[j];
     s3[cont]=x[l];
      cont++;
    }
 cont--;
 ok=cont;
 qsort(1,ok);
 ok=0;
 for(i=1;i<=cont;i++)
  if(y=calcul(1,cont,m-s[i]))
  {
   po[1]=s1[i];
   po[2]=s2[i];
   po[3]=s3[i];
   po[4]=s1[y];
   po[5]=s2[y];
   po[6]=s3[y];
   qsort2(1,6);
   for(j=1;j<=6;j++)
    g<<po[j]<<" ";
   ok=1;
   break;
  }
 if(ok==0)
  g<<"-1";
 f.close();
 g.close();
 return 0;
}