Cod sursa(job #56585)

Utilizator wazupPricop Mircea wazup Data 29 aprilie 2007 23:06:42
Problema Loto Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <stdio.h>
#include <stdlib.h>
FILE *fin,*fout;
struct tr { long long a,b,c,val; };
tr sums[1000001];
long long poz,hsize,n,i,j,k,s,l,a[101];

long long find(long long val)
 {
     long long st=1,dr=l,mij;
     while (st<=dr)
        {  mij=(st+dr)/2;
           if (sums[mij].val==val)
             return mij;
           else
             if (sums[mij].val<val)
               st=mij+1;
             else
               dr=mij-1;
        }
     return 0;
 }


void reheap (int i)
 { int l=2*i,r=2*i+1,max=i;
   tr aux;
   if (l<=hsize&&sums[l].val>sums[i].val)
      max=l;
   if (r<=hsize&&sums[r].val>sums[max].val)
      max=r;
   if (max!=i)
     { aux=sums[max];
       sums[max]=sums[i];
       sums[i]=aux;
       reheap(max);
     }
 }


void hsort()
 { hsize=l;
   tr aux;
   int i;
   for (i=l/2;i>=1;i--)
      reheap(i);
   for (i=l;i>=2;i--)
      {  aux=sums[1];
         sums[1]=sums[i];
         sums[i]=aux;
         hsize--;
         reheap(1);
      }
 }


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