Cod sursa(job #2333336)

Utilizator Sh1fTieKrecht Abel Sh1fTie Data 31 ianuarie 2019 21:28:15
Problema Loto Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <iostream>
#include <fstream>

using namespace std;

#define MAXN 100
#define LOTONUM 6

int arrNum[MAXN];
int maxVal = 0;
int iNr;
int iSum;
int arrRes[LOTONUM];

void beolvas()
{
    ifstream fin;
    fin.open("loto.in");

    fin>> iNr >> iSum;

    for (int i=0;i<iNr;i++)
    {
        fin>> arrNum[i];
        if (arrNum[i]>maxVal)
        {
            maxVal = arrNum[i];
        }
    }

    fin.close();
    return;
}

bool bcktrkCheck(const int sum, const int i)
{
    if(i<LOTONUM)
    {
        if ((LOTONUM-i-1)!=0)
        {
            if ((iSum - sum)/(LOTONUM-i-1)> maxVal)
            {
                return false;
            }
        }

        return true;
    }
    else
    {
        return false;
    }
}

bool Backtrack(int sum, int i)
{
    if (sum == iSum && i == LOTONUM)
    {
        return true;
    }
    else if(i>LOTONUM || sum >iSum)
    {
        return false;
    }
    for (int j=0;j<iNr;j++)
    {
        arrRes[i] = arrNum[j];

        sum+=arrNum[j];

        if (bcktrkCheck(sum,i))
        {
            if (Backtrack(sum, i+1))
            {
                return true;
            }
        }
        sum-=arrNum[j];
        arrRes[i] = 0;
    }

    return false;
}

int main()
{
    beolvas();
    if (Backtrack(0,0))
    {
        for (int i=0;i<LOTONUM;i++)
        {
            cout << arrRes[i] << " ";
        }
    }
    else
    {
        cout << "-1";
    }
}