Cod sursa(job #56593)

Utilizator wazupPricop Mircea wazup Data 29 aprilie 2007 23:42:11
Problema Loto Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <stdio.h>
FILE *fin,*fout;
long sums[1000001],as[1000001],bs[1000001],cs[1000001];
long poz,hsize,n,i,j,k,s,l,a[101],auxa,auxb,auxc,auxs,x,y;




long find(long val)
 {
     int i, step;
     for (step = 1; step <= l; step <<= 1);
     for (i = 0; step; step >>= 1)
         if (i + step <= l && sums[i + step] <= val)
            i += step;
     if (sums[i]==val)
     return i;
     return 0;
 }


void reheap (int i)
 { int l=2*i,r=2*i+1,max=i;
   long aux;
   if (l<=hsize&&sums[l]>sums[i])
      max=l;
   if (r<=hsize&&sums[r]>sums[max])
      max=r;
   if (max!=i)
     {    x=i;
          y=max;
          auxs=sums[x];
          auxa=as[x];
          auxb=bs[x];
          auxc=cs[x];
          sums[x]=sums[y];
          as[x]=as[y];
          bs[x]=bs[y];
          cs[x]=cs[y];
          sums[y]=auxs;
          as[y]=auxa;
          bs[y]=auxb;
          cs[y]=auxc;
          reheap(max);
     }
 }


void hsort()
 { hsize=l;
   long aux;
   int i;
   for (i=l/2;i>=1;i--)
      reheap(i);
   for (i=l;i>=2;i--)
      {
         x=1;
          y=i;
          auxs=sums[x];
          auxa=as[x];
          auxb=bs[x];
          auxc=cs[x];
          sums[x]=sums[y];
          as[x]=as[y];
          bs[x]=bs[y];
          cs[x]=cs[y];
          sums[y]=auxs;
          as[y]=auxa;
          bs[y]=auxb;
          cs[y]=auxc;
       hsize--;
         reheap(1);
      }
 }


int main()
{
 fin=fopen("loto.in","rt");
 fout=fopen("loto.out","wt");
 fscanf(fin,"%ld %ld",&n,&s);
 for (i=1;i<=n;i++)
    fscanf(fin,"%ld",&a[i]);
 l=1;
 for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
       for (k=1;k<=n;k++)
        if (a[i]+a[j]+a[k]<=s)
          {
          sums[l]=a[i]+a[j]+a[k];
          as[l]=a[i];
          bs[l]=a[j];
          cs[l]=a[k];
          l++;
         }
 l--;
 hsort();
 for (i=1;i<=l;i++)
       { if (s-sums[i]<=sums[l]&&sums[i]!=sums[i-1])
         {
          poz=find(s-sums[i]);
         if (poz)
         { fprintf(fout,"%ld %ld %ld %ld %ld %ld\n",as[i],bs[i],cs[i],as[poz],bs[poz],cs[poz]);
           return 0;
         }
         }
       }
 fprintf(fout,"-1\n");
 return 0;
}