Cod sursa(job #600354)

Utilizator luckyme91wiz kid luckyme91 Data 1 iulie 2011 14:46:21
Problema Loto Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> num, Sol;
int s;
int bin (int begin, int end, int x)
{
	if (begin <= end)
	{	int temp = (begin + end)/2 ;
		if (x > num[temp])
			return bin (temp + 1, end, x);
		if (x < num[temp])
			return bin (begin, temp - 1, x);
		if (x == num[temp])
			return temp;
	}
	if (end > 0)
		return end;
	else
		return -1;
}	
		

int solve (vector <int> sol,int sum, int end,int  ix)
{
	if (sol[5] != 0 && sum == 0)
	{
		Sol = sol;
		return 1;
	}
	if (ix <= 5)
	{
		int x = bin (0, end, sum), i;
		for (i = x; i >= 0; i--)
			if (sum - num[i] >= 0 && (s - sum) + num[i] * (6 - ix) >= s && (s - sum) + num[0]*(6 - ix) <= s) 
			{	
				sol[ix] = num[i];
				if (solve (sol, sum - num[i], x, ix + 1))
					return 1;
			}
	}
	return 0;

}
	


int main() {

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

int n, x, i;

in >> n >> s;
vector <int> sol(6, 0);

for (; n > 0; n--)
{
	in >> x;
	num.push_back(x);
}
sort (num.begin(), num.begin() + num.size() - 1);
solve (sol, s, num.size() - 1, 0);
if (Sol.size() == 6)
	for (i = 5; i >= 0; i--)
		out << Sol[i] << " ";
else
	out << -1;
return 0;
}