Cod sursa(job #56667)

Utilizator cezar305Mr. Noname cezar305 Data 30 aprilie 2007 09:35:52
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <fstream.h>
#include <iomanip.h>

fstream fin("loto.in",ios::in);
fstream fout("loto.out",ios::out);

long n,v[110],s,i,i1,i2,i3,i4,i5,i6,lmin,lmax,suma,t;

void qsort(long ii,long is){
  long i=ii,j=is,aux;
  while (i!=j){
    while ((v[i]<=v[j])&&(i!=j)) j--;
    if (i==j) break;
    aux=v[i];v[i]=v[j];v[j]=aux; i++;
    while ((v[i]<=v[j])&&(i!=j)) i++;  
    if (i==j) break;
    aux=v[i];v[i]=v[j];v[j]=aux;j--;    
  }       
  if (ii<i-1) qsort(ii,i-1);
  if (i+1<is) qsort(i+1,is);
}    

long cauta(long x,long ls,long ld){
  long m=(ls+ld)/2;
  if (x==v[m]) return m;
  if (ls>ld)
     return 0;
  if (x<v[m])
     return cauta(x,ls,m-1);
  else
      return cauta(x,m+1,ld);
}    

int main(){
  fin>>n>>s;
  for (i=1;i<=n;i++) fin>>v[i];
  qsort(1,n);
  if (6*v[1]>s || 6*v[n]<s) {fout<<-1;fin.close();fout.close();return 0;}
  lmin=1;lmax=n;
    while (5*v[n]+v[lmin]<s) lmin++;
    while (5*v[lmin]+v[lmax]>s) lmax--;
  for (i1=lmin;i1<=lmax;i1++){
    if (6*v[i1]>s) i1=lmax+1;
    else for (i2=i1;i2<=lmax;i2++){
      if (v[i1]+5*v[i2]>s) i2=lmax+1;
      else for (i3=i2;i3<=lmax;i3++){
        if (v[i1]+v[i2]+4*v[i3]>s) i3=lmax+1;
        else for (i4=i3;i4<=lmax;i4++){
          if (v[i1]+v[i2]+v[i3]+3*v[i4]>s) i4=lmax+1;
          else for (i5=i4;i5<=lmax;i5++){
            if (v[i1]+v[i2]+v[i3]+v[i4]+2*v[i5]>s) i5=lmax+1;  
            else {
                 t=cauta(s-v[i1]-v[i2]-v[i3]-v[i4]-v[i5],1,n);
                 if (t!=0)
                    {
                    fout<<v[i1]<<" "<<v[i2]<<" "<<v[i3]<<" "<<
                    v[i4]<<" "<<v[i5]<<" "<<t;
      fin.close();fout.close();return 0;
    }
  }}}}}}    
  fout<<-1;
  fin.close();fout.close();        
return 0;
}