Cod sursa(job #127695)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 24 ianuarie 2008 21:40:00
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
//loto
#include<stdio.h>
#include<iostream.h>
#include<conio.h>
FILE*fin=fopen("loto.in","r");
FILE*fout=fopen("loto.out","w");
int sp[100001],s1[100001],s2[100001],s3[100001],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);
  }
  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)
  {
    if((s1[nod]+s2[nod]+s3[nod])!=sp[nod]&&d!=dim)
    aux=sp[nod];sp[nod]=sp[nd];sp[nd]=aux;
    aux=s1[nod];s1[nod]=s1[nd];s1[nd]=aux;
    aux=s2[nod];s2[nod]=s2[nd];s2[nd]=aux;
    aux=s3[nod];s3[nod]=s3[nd];s3[nd]=aux;
    if((s1[nod]+s2[nod]+s3[nod])!=sp[nod]&&d!=dim)
    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;
    aux=s1[1];s1[1]=s1[da];s1[da]=aux;
    aux=s2[1];s2[1]=s2[da];s2[da]=aux;
    aux=s3[1];s3[1]=s3[da];s3[da]=aux;
    da--;
    if(da>1) rech(1,da);
  }
}

int main()
{
  int s,i,j,k,n,v[101],p1,p2,p3,p4,p5,p6,p;
  clrscr();
  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];
	s1[dim]=v[i];
	s2[dim]=v[j];
	s3[dim]=v[k];
      }
  ord();
  for(i=1;i<=dim;i++)
  {
    p=cb(1,dim,s-sp[i]);
    if(p!=-1)
    {
      p1=s1[i];p2=s2[i];p3=s3[i];p4=s1[p];p5=s2[p];p6=s3[p];
      break;
    }
  }
  if(p==-1) fprintf(fout,"%d",-1);
  else fprintf(fout,"%d%c%d%c%d%c%d%c%d%c%d",p1,' ',p2,' ',p3,' ',p4,' ',p5,' ',p6);
  fclose(fin);
  fclose(fout);
  return 0;
}