Cod sursa(job #136974)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 16 februarie 2008 18:09:06
Problema Loto Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 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];

long part(long st, long dr)
{
 long i=st, j=dr, s=-1;
 trip aux;
 while (i<j)
   {
    if (su[i].ss>su[j].ss)
      {
       aux=su[i];
       su[i]=su[j];
       su[j]=aux;
       s=-s;
      }
    if (s==1) i++;
         else j--;
   }
 return i;
}

void qsort(long st, long dr)
{
 long p;
 if (st<dr)
   {
    p=part(st,dr);
    qsort(st,p-1);
    qsort(p+1,dr);
   }
}

long find(long vl,long poz)
{
 long st,dr,mij;
 if (su[poz].ss>vl) { st=1; dr=poz-1; }
   else { 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 ;
     }
  }
 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].ss=nr[i]+nr[j]+nr[k];
        su[l].a=nr[i];
        su[l].b=nr[j];
        su[l].c=nr[k];
       }
       
 qsort(1,l);
 
 solve();
 
 return 0;
}