Cod sursa(job #40810)

Utilizator razvi9Jurca Razvan razvi9 Data 27 martie 2007 19:18:21
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include<stdio.h>
int a[101],n,i,j,k,S,nr;
struct {int i,j,k,s;} s[1000],aux;
int poz(int st,int dr)
{int plusst=0,plusdr=-1;
 while(st<dr)
 {if(s[st].s>s[dr].s) {aux=s[st];s[st]=s[dr];s[dr]=aux;}
  st=st+plusst;
  dr=dr+plusdr;}
 return st;}
void qsort(int st,int dr)
{int k=poz(st,dr);
 if(st>=dr) return ;
 qsort(st,k-1);
 qsort(k+1,dr);}
int bsearch(int st,int dr,int S)
{int mij=st+dr;
 mij/=2;
 if(s[st].s==S) return st;
 if(s[st].s>S||st>dr) return 0;
 if(st==dr) if(s[st].s==S) return st;
 else 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(j=1;j<=i;j++)
  for(k=1;k<=j;k++)
  s[++nr].i=i,s[nr].j=j,s[nr].k=k,s[nr].s=a[i]+a[j]+a[k];
  }
 qsort(1,nr);
 for(i=1;i<=n;i++)
  {j=bsearch(1,nr,S-s[i].s);
   if(j)
   {printf("%d %d %d %d %d %d",a[s[i].i],a[s[i].j],a[s[i].k],a[s[j].i],a[s[j].j],a[s[j].k]);
    fclose(stdout);
	return 0;}}
 printf("-1");
 fclose(stdout);
 return 0;}