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