Cod sursa(job #363786)

Utilizator loginLogin Iustin Anca login Data 14 noiembrie 2009 18:33:22
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
# include <fstream>
using namespace std;
ofstream fout ("loto.out");
struct sol {int b, e;};
sol x[103]; 
int n, sum, a[105], pp;

int afis (int k)
{
    for (int i=1;i<=k;i++)
        for (int j=1;j<=x[i].e;j++)
            fout<<a[x[i].b]<<" ";
    pp=1;
}    

void bk (int k, int e, int s)
{
    int j;
    for (int i=x[k-1].b+1;i<=n && pp==0;i++)
    {
        for (e<sum/a[i]?j=e:j=(sum/a[i]);j>=0 && pp==0;j--)
        {
            x[k].b=i;
            x[k].e=j;
            if (s+(a[x[k].b]*j)==sum && e-j==0)
               afis (k);
            else if (e-j>0)
               bk(k+1, e-j, s+(a[x[k].b]*j));     
        }
    }        
}        

int main ()
{
    ifstream fin ("loto.in");
    fin>>n>>sum;
    for (int i=1;i<=n;i++)
        fin>>a[i];
    bk (1, 6, 0);
    if (pp==0)
        fout<<"-1";
    return 0;
}