Cod sursa(job #137090)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 16 februarie 2008 21:30:56
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
# include <stdio.h>

# define nmax 101
# define mmax 1030301
# define FIN "loto.in"
# define FOUT "loto.out"

long n,nr[nmax],s,i,l=0,su[mmax];

void heapsort(long n)
{
 long i,j,k,aux;
 for (i=1; i<=n; i++)
   {
    j=i;
    while (j/2!=0&&su[j/2]<su[j])
      {
       aux=su[j/2];
       su[j/2]=su[j];
       su[j]=aux;
       j=j/2;
      }
   }
 i=n;
 while (i>1)
   {
    aux=su[1];
    su[1]=su[i];
    su[i]=aux;
    i--; j=1;
    while (j>0)
      {
       k=2*j;
       if (k>i) break;
       if (k+1<=i&&su[k+1]>su[k]) k++;
       if (su[j]>su[k]) break;
       aux=su[j];
       su[j]=su[k];
       su[k]=aux;
       j=k;
      }
   }
}

void afis(long nn)
{
 long a,b,c;
 for (a=1; a<=n; a++)
   for (b=a; b<=n; b++)
     for (c=b; c<=n; c++)
       if (nr[a]+nr[b]+nr[c]==su[nn])
         {
          printf("%ld %ld %ld",nr[a],nr[b],nr[c]);
          return;
          }
}

void solve()
{
 long aux,i,k=l;
 for (long i=1; i<=l&&k>0; i++)
   {
    while (su[i]+su[k]>s && k>0) k--;
    if (k<=0) break; 
    if (su[i]+su[k]==s)
     {
      afis(i);
      printf(" ");
      afis(k);
      return ;
     }
  }
 printf("-1");
}

int main()
{
 freopen(FIN,"r",stdin);
 freopen(FOUT,"w",stdout);
 scanf("%ld %ld",&n,&s);
 
 for (i=1; i<=n; i++)
   scanf("%ld",&nr[i]);
   
 for (i=1; i<=n; i++)
   for (long j=i; j<=n; j++)
     for (long k=j; k<=n; k++)
       {
        su[++l]=nr[i]+nr[j]+nr[k];
       }      
 
 heapsort(l);
 
 solve();
 
 return 0;
}