Cod sursa(job #127722)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 24 ianuarie 2008 22:25:41
Problema Loto Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 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;
}
void rech(int nod,int d)
{
  int max=sp[nod],ls,rs,nd,aux;
  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)
  {
    aux=sp[nod];sp[nod]=sp[nd];sp[nd]=aux;
    rech(nd,d);
  }
}
void ord()
{
  int i,aux;
  for(i=dim/2;i>=1;i--)
    rech(i,dim);
  int da=dim;
  while(da>1)
  {
    aux=sp[1];sp[1]=sp[da];sp[da]=aux;
    da--;
    if(da>1) rech(1,da);
  }
}

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=1;j<=n;j++)
      {
        if(g1) break;
        for(k=1;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=1;j<=n;j++)
      {
        if(g2) break;
        for(k=1;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;
}