Mai intai trebuie sa te autentifici.
Cod sursa(job #276598)
Utilizator | 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;
}