Cod sursa(job #786003)

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

using namespace std;

#define MAXN 102
#define MAXS 1000001

int v[ MAXN ], s[ MAXS ][4];
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;
		}
	}
}

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];
			
	for(i = 1; i <= nrs; ++i)
	{
		p = bs(sum - s[i][0]);
		if(s[p][0] + s[i][0] == sum)
		{	
			fprintf(g, "%d %d %d %d %d %d\n", s[i][1], s[i][2], s[i][3], s[p][1], s[p][2], s[p][3]);
			fclose(g);
			return 0;
		}
	}
	
	fprintf(g, "%d\n", -1);

	fclose(g);
	
	return 0;
}