Cod sursa(job #133240)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 7 februarie 2008 22:39:51
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.22 kb
//loto
#include<stdio.h>
FILE*fin=fopen("loto.in","r");
FILE*fout=fopen("loto.out","w");
int sp[1000001],dim;
int cb(int st,int dr,int val)
{
  if(st<=dr)
  {
    int mij=(st+dr)>>1;
    if(sp[mij]==val) return mij;
    else if(val<sp[mij]) return cb(st,mij-1,val);
	 else return cb(mij+1,dr,val);
  }
  else return -1;
}
int pos(int li, int ls)  
  {  
   int i=0,j=-1,aux;  
   while(li<ls)  
       {if(sp[li]>=sp[ls])  
          {sp[li]^=sp[ls]^sp[li]^=sp[ls];  
           aux=i;i=-j;j=-aux;}  
        li+=i;  
        ls+=j;}  
   return li;  
  }  
  
void qs(int li, int ls)  
{  
   if(li<ls)  
     {int k=pos(li,ls);  
      qs(li,k-1);  
      qs(k+1,ls);}  
}   
/*void rech(int nod,int d)
{
  int max=sp[nod],ls,rs,nd;
  nd=nod;ls=nod<<1;rs=ls+1;
  if(ls<=d&&sp[ls]>max){max=sp[ls];nd=ls;}
  if(rs<=d&&sp[rs]>max){max=sp[rs];nd=rs;}
  if(nd!=nod)
  {
    sp[nod]^=sp[nd]^=sp[nod]^=sp[nd];
    rech(nd,d);
  }
}*/
void ord()
{
  /*int i,aux;
  for(i=dim/2;i>=1;i--)
    rech(i,dim);
  int da=dim;
  while(da>1)
  {
    sp[1]^=sp[da]^=sp[1]^=sp[da];
    da--;
    if(da>1) rech(1,da);
  }*/
  qs(1,dim);
}

int main()
{
  int s,i,j,k,n,v[1000],p;
  
  fscanf(fin,"%d%d",&n,&s);
  for(i=1;i<=n;i++)
    fscanf(fin,"%d",&v[i]);
  dim=0;
  for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
      for(k=1;k<=n;k++)
      {
	dim++;
	sp[dim]=v[i]+v[j]+v[k];
      }
  ord();
  p=-1;
  for(i=1;i<=dim;i++)
  {
    p=cb(1,dim,s-sp[i]);
    if(p!=-1)
          break;
  }
  if(p==-1) fprintf(fout,"%d",-1);
  else
  {
    int g1=0,g2=0,pp=i;
    for(i=1;i<=n;i++)
    {
      if(g1) break;
      for(j=i;j<=n;j++)
      {
        if(g1) break;
        for(k=j;k<=n;k++)
        {
          if(sp[pp]==v[i]+v[j]+v[k]){g1=1;fprintf(fout,"%d%c%d%c%d%c",v[i],' ',v[j],' ',v[k],' ');}
          if(g1) break;
        }  
      }
    }
    for(i=1;i<=n;i++)
    {
      if(g2) break;
      for(j=i;j<=n;j++)
      {
        if(g2) break;
        for(k=j;k<=n;k++)
        {
          if(sp[p]==v[i]+v[j]+v[k]){g2=1;fprintf(fout,"%d%c%d%c%d",v[i],' ',v[j],' ',v[k]);}
          if(g2) break;
        }  
      }
    }
  }
  fclose(fin);
  fclose(fout);
  return 0;
}