Cod sursa(job #133096)

Utilizator stef2nStefan Istrate stef2n Data 7 februarie 2008 15:12:00
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <stdio.h>

#define infile "loto.in"
#define outfile "loto.out"
#define NMAX 102
FILE *fin,*fout;
int n,val[NMAX];
int n3,s3[NMAX*NMAX*NMAX],cine1[NMAX*NMAX*NMAX],cine2[NMAX*NMAX*NMAX];
int suma;

void citire()
  {
   fin=fopen(infile,"r");
   fscanf(fin,"%d %d",&n,&suma);
   for(int i=0;i<n;i++)
      fscanf(fin,"%d",&val[i]);
   fclose(fin);
  }

int pos(int li, int ls)
  {
   int i=0,j=-1,aux;
   while(li<ls)
       {if(s3[li]>=s3[ls])
          {aux=s3[li];s3[li]=s3[ls];s3[ls]=aux;
           aux=cine1[li];cine1[li]=cine1[ls];cine1[ls]=aux;
           aux=cine2[li];cine2[li]=cine2[ls];cine2[ls]=aux;
           aux=i;i=-j;j=-aux;}
        li+=i;
        ls+=j;}
   return li;
  }

void quicksort(int li, int ls)
  {
   if(li<ls)
     {int k=pos(li,ls);
      quicksort(li,k-1);
      quicksort(k+1,ls);}
  }

void initializari()
  {
   int i,j,k,poz;
   n3=0;
   for(i=0;i<n;i++)
      for(j=i;j<n;j++)
         for(k=j;k<n;k++)
            {s3[n3]=val[i]+val[j]+val[k];
             cine1[n3]=val[i];
             cine2[n3]=val[j];
             n3++;}
   quicksort(0,n3-1);
  }

int binary_search(int value, int li, int ls)
  {
   if(li>ls)
     return -1;
   int mij=(li+ls)/2;
   if(s3[mij]==value)
     return mij;
   if(s3[mij]>value)
     return binary_search(value,li,mij-1);
   return binary_search(value,mij+1,ls);
  }


int main()
{
citire();
initializari();
int poz;
fout=fopen(outfile,"w");
for(int i=0;i<n;i++)
   for(int j=i;j<n;j++)
      for(int k=j;k<n;k++)
         {poz=binary_search(suma-val[i]-val[j]-val[k],0,n3-1);
          if(poz!=-1)
           {fprintf(fout,"%d %d %d %d %d %d\n",val[i],val[j],val[k],cine1[poz],cine2[poz],s3[poz]-cine1[poz]-cine2[poz]);
            fclose(fout);
            return 0;}}
fprintf(fout,"-1\n");
fclose(fout);
return 0;
}