Cod sursa(job #786009)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 10 septembrie 2012 12:51:51
Problema Loto Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include<stdio.h>
#include<fstream>
#include<algorithm>

using namespace std;

#define MAXN 102
#define MAXS 1000001

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

void qsort(int left, int right)
{
	int i = left, j = right, tmp, pivot = s[(left + right)/2][0];
	
	while(i <= j)
	{
		while(s[i][0] < pivot) ++i;
		while(s[j][0] > pivot) --j;
		
		if(i <= j)
		{
			tmp = s[i][0], s[i][0] = s[j][0], s[j][0] = tmp;
			tmp = s[i][1], s[i][1] = s[j][1], s[j][1] = tmp;
			tmp = s[i][2], s[i][2] = s[j][2], s[j][2] = tmp;
			tmp = s[i][3], s[i][3] = s[j][3], s[j][3] = tmp;
			++i, --j;
		}
	}
	if(left < j)
		qsort(left, j);
	if(i < right)
		qsort(i, right);
}

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

int main()
{
	ifstream f("loto.in");
	
	f >> n >> sum;
	for(i = 1; i <= n; ++i)
		f >> v[i];
	
	f.close();
	
	sort(v + 1, v + n + 1);
	
	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 = 1; j <= n; ++j)
			for(k = 1; k <= n; ++k)
				nrs++, s[nrs][0] = v[i] + v[j] + v[k], s[nrs][1] = v[i], s[nrs][2] = v[j], s[nrs][3] = v[k];
			
	qsort(1, nrs);
			
	for(i = 1; i <= nrs; ++i)
	{
		p = bs(sum - s[i][0]);
		if(s[p][0] + s[i][0] == sum)
		{	
			sol[1] = s[i][1], sol[2] = s[i][2], sol[3] = s[i][3], sol[4] = s[p][1], sol[5] = s[p][2], sol[6] = s[p][3];
			sort(sol + 1, sol + 7);
			for(j = 1; j <= 6; ++j)
				fprintf(g, "%d ", sol[j]);
			fprintf(g, "\n");
			fclose(g);
			return 0;
		}
	}
	
	fprintf(g, "%d\n", -1);

	fclose(g);
	
	return 0;
}