Cod sursa(job #1878852)

Utilizator loghin.alexandruLoghin Alexandru loghin.alexandru Data 14 februarie 2017 15:34:39
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream fin("loto.in");
ofstream fout("loto.out");

vector<unsigned int> lottery;

unsigned int solution[6] = {};

bool found, stop;
unsigned int partialSum;

void printSolution()
{
	for (unsigned int i = 0; i < 6; ++i)
	{
		fout << solution[i] << ' ';
	}
}

bool checkSolution(unsigned int sum)
{
	unsigned int sumSol = 0;
	for (unsigned int i = 0; i < 6; ++i)
	{
		sumSol += solution[i];
	}
	if (sumSol == sum) { return true; }
	else return false;
}


void backLotto(unsigned int k, unsigned int sum, bool ok)
{
	for (auto it = lottery.begin(); it != lottery.end(); ++it)
	{
		if (stop == true)
		{
			partialSum -= solution[k];
		}
		if (((partialSum + (*it)) <= sum) || it == lottery.end() - 1)
		{
			partialSum += *it;
			solution[k] = *it;
			ok = true;
			if (k == 5) { stop = true; }
		}
		if (checkSolution(sum) && stop && found == false)
		{
			printSolution();
			found = true;
		}
		else
		{
			if (ok && stop == false)
			{
				backLotto(k + 1, sum, false);
			}
		}
	}
}

int main()
{

	unsigned int lotteryNumbers = 0, sum = 0, maxNum = 0;
	fin >> lotteryNumbers >> sum;
	for (unsigned int i = 0; i < lotteryNumbers; i++)
	{
		unsigned int x;
		fin >> x;
		if (x > maxNum)
		{
			maxNum = x;
		}
		lottery.push_back(x);
	}
	sort(lottery.begin(), lottery.end(), [](int a, int b) {if (a > b)return true; else return false; });
	if (maxNum * 6 < sum)
	{
		fout << -1;
		return 0;
	}
	backLotto(0, sum, false);

	return 0;
}