Cod sursa(job #137088)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 16 februarie 2008 21:28:52
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
# include <stdio.h>   
  
# define nmax 101   
# define mmax 1030301   
# define FIN "loto.in"   
# define FOUT "loto.out"   
  
struct trip {long ss; long a; long b; long c;};   
  
long n,nr[nmax],s,i,l=0;   
trip su[mmax];   
  
void heapsort(long n)   
{   
 long i,j,k;
 trip aux;   
 for (i=1; i<=n; i++)   
   {   
    j=i;   
    while (j/2!=0&&su[j/2].ss<su[j].ss)   
      {   
       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].ss>su[k].ss) k++;   
       if (su[j].ss>su[k].ss) break;   
       aux=su[j];   
       su[j]=su[k];   
       su[k]=aux;   
       j=k;   
      }   
   }   
}   
  
long find(long vl,long poz)   
{   
 long st,dr,mij;   
 st=poz; dr=l;
 while (st<=dr)   
   {   
    mij=(st+dr)/2;   
    if (su[mij].ss==vl) return mij;   
      else  
        if (su[mij].ss>vl) dr=mij-1;   
                      else st=mij+1;    
   }   
 return 0;   
}   
  
void solve()   
{   
 long aux,i;   
 for (long i=1; i<=l; i++)   
  if (su[i].ss<=s-su[i].ss)   
  {   
   aux=find(s-su[i].ss,i);    
   if (aux!=0)    
     {   
      printf("%ld %ld %ld ",su[i].a,su[i].b,su[i].c);   
      printf("%ld %ld %ld",su[aux].a,su[aux].b,su[aux].c);   
      return ;   
     }   
  }  else { printf("-1"); return; }   
}   
  
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].ss=nr[i]+nr[j]+nr[k];   
        su[l].a=nr[i];   
        su[l].b=nr[j];   
        su[l].c=nr[k];   
       }   
          
 heapsort(l);   
    
 solve();   
    
 return 0;   
}