Cod sursa(job #53502)

Utilizator razvi9Jurca Razvan razvi9 Data 22 aprilie 2007 13:08:34
Problema Loto Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<stdio.h>
int a[101],n,i,j,k,S,nr;
struct {int i,j,k;int s;} s[1000001],aux;
int poz(int st,int dr)
{int y=0,x=-1,au;
 while(st<dr)
 {if(s[st].s>s[dr].s)
   {aux=s[st];s[st]=s[dr];s[dr]=aux;
    au=y;y=-x;x=-au;}
  st=st+y;
  dr=dr+x;}
 return st;
}
void qsort(int stanga,int dreapta)
{if(stanga>=dreapta) return ;
 int k=poz(stanga,dreapta);
 qsort(stanga,k-1);
 qsort(k+1,dreapta);}
int bsearch(int st,int dr,long S)
{int mij=st+dr;
 mij/=2;
 if(st>dr) return 0;
 if(s[mij].s==S) return mij;
 if(s[mij].s<S) return bsearch(mij+1,dr,S);
 return bsearch(st,mij-1,S);}
int main()
{freopen("loto.in","r",stdin);
 freopen("loto.out","w",stdout);
 scanf("%d %d",&n,&S);
 for(i=1;i<=n;i++)
 {scanf("%d",&a[i]);}
 for(i=1;i<=n;i++)
  for(j=i;j<=n;j++)
   for(k=j;k<=n;k++)
    s[++nr].s=a[i]+a[k]+a[j],s[nr].i=a[i],s[nr].j=a[j],s[nr].k=a[k];
 qsort(1,nr);
 for(i=1;i<=nr;i++)
  {j=bsearch(1,nr,S-s[i].s);
   if(j)
   {printf("%d %d %d %d %d %d",s[i].i,s[i].j,s[i].k,s[j].i,s[j].j,s[j].k);
    fclose(stdout);
    return 0;}}
 printf("-1");
 fclose(stdout);
 return 0;}