Mai intai trebuie sa te autentifici.

Cod sursa(job #276598)

Utilizator Sorin_IonutBYSorynyos Sorin_Ionut Data 11 martie 2009 11:28:03
Problema Loto Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
////////// back (culmea :p) ///////////////////

#include <iostream.h>
#include <fstream.h>

#define MAXN 10001
#define IN "loto.in"
#define OUT "loto.out"

ifstream fin(IN);
ofstream fout(OUT);

long n,s,sw=1;
long part;
long v[MAXN],val[MAXN];

void cit();
void back(long);
void afis();
long poz(long,long);
void quick(long,long);

int main()
{
 long i;

 cit();
  fin.close();

 for(i=1;(i<=n && sw);i++)
 {
  v[1]=i;
  part=val[i];
  back(2);
 }
 
 afis();
 fout.close();

 return 0;
}

void cit()
{
 long i;

 fin>>n>>s;
 for(i=1;i<=n;i++)
  fin>>val[i];
 quick(1,n);
}

void back(long k)
{
 long i;

 if(k==7 && part==s)
 {
  sw=0;
  afis();
  fout.close();
  return;
 }
 else
  if(k<7)
   for(i=v[k-1];i>=1;i--)
    if(part+val[i]<=s)
    {
     v[k]=i;
     part+=val[i];
     back(k+1);
     part-=val[i];
    }
}

void afis()
{
 long i;

 if(sw==1)
  fout<<"-1"<<endl;
 else
  for(i=1;i<=6;i++)
   fout<<val[v[i]]<<" ";
}

void quick(long st,long dr)
{
 if(st<dr)
 {
  long k=poz(st,dr);
  quick(st,k-1);
  quick(k+1,dr);
 }
}

long poz(long st,long dr)
{
 long i=st;
 long j=dr;
 long ii=0;
 long jj=-1;
 long aux;
 
 while(i<j)
 {
  if(val[i]<val[j])
  {
   aux=val[i];
   val[i]=val[j];
   val[j]=aux;
   
   aux=ii;
   ii=-jj;
   jj=-aux;
  }
  i=i+ii;
  j=j+jj;
 }
return i;
}