Cod sursa(job #786014)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 10 septembrie 2012 13:00:36
Problema Loto Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include<stdio.h>
#include<fstream>
#include<algorithm>

using namespace std;

#define MAXN 102
#define MAXS 1000001

int v[ MAXN ], s[ MAXS ];
int n, sum, i, j, k, nrs, p, aux;

int bs(int x)
{
	int left = 1, right = nrs, mid;
	
	while(left <= right)
	{
		mid = (left + right) / 2;
		
		if(s[mid] > x)
			right = mid - 1;
		else if(s[mid] < x)
			left = mid + 1;
		else return 1;
	}
	
	return 0;
}

int main()
{
	ifstream f("loto.in");
	
	f >> n >> sum;
	for(i = 1; i <= n; ++i)
		f >> v[i];
	
	f.close();

	
	FILE *g = fopen("loto.out", "w");
	
	if(sum > v[n] * 6)
	{
		fprintf(g, "-1\n");
		return 0;
	}
	
	for(i = 1; i <= n; ++i)
		for(j = i; j <= n; ++j)
			for(k = j; k <= n; ++k)
				nrs++, s[nrs] = v[i] + v[j] + v[k];
			
	sort(s + 1, s + nrs + 1);
			
	for(i = 1; i <= nrs; ++i)
	{
		p = bs(sum - s[i]);
		if(p)
		{	
			aux = s[i];
			for(i = 1; i <= n; ++i)
				for(j = 1; j <= n; ++j)
					for(k = 1; k <= n; ++k)
						if(v[i] + v[j] + v[k] == aux)
							fprintf(g, "%d %d %d ", v[i], v[j], v[k]), i = j = k = n + 1;
			for(i = 1; i <= n; ++i)
				for(j = 1; j <= n; ++j)
					for(k = 1; k <= n; ++k)
						if(v[i] + v[j] + v[k] == sum - aux)
							fprintf(g, "%d %d %d\n", v[i], v[j], v[k]), i = j = k = n + 1;	
			return 0;			
		}
	}
	
	fprintf(g, "%d\n", -1);

	fclose(g);
	
	return 0;
}