Cod sursa(job #56408)

Utilizator wazupPricop Mircea wazup Data 29 aprilie 2007 15:33:28
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <stdio.h>
FILE *fin,*fout;
long long poz,hsize,sums[1000001],n,a[101],i,j,k,s,l,as[1000001],bs[1000001],cs[1000001];

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


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


void hsort()
{
 int i,aux;
 hsize=l;
 for (i=l/2;i>=1;i--)
    reheap(i);
 for (i=l;i>=2;i--)
    { aux=sums[1];
      sums[1]=sums[hsize];
      sums[hsize]=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]=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 (find(s-sums[i],poz))
       { fprintf(fout,"%lld %lld %lld %lld %lld %lld\n",as[i],bs[i],cs[i],as[poz],bs[poz],cs[poz]);
         return 0;
       }
    else
      while (sums[i]==sums[i+1])
        i++;
 fprintf(fout,"-1\n");
 return 0;
}