Cod sursa(job #1053036)

Utilizator rucarRucareanu Alexandru rucar Data 12 decembrie 2013 01:27:40
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>

struct suma{
	int val, i, j, k;
};
suma sume[200000];
int cautare(suma *s, int size, int inf)
{
	int putere = (1 << 20);
	int poz = 0;
	while (putere)
	{
		if (poz + putere < size && s[poz + putere].val <= inf)
			poz += putere;
		putere <<= 1;
		if (s[poz].val == inf)
			return poz;
	}
	return -1;
}

int cmp(suma s1, suma s2)
{
	if (s1.val > s2.val)
		return 1;
	else return 0;
}

int main()
{
	int n, i, s, j, k, nr = 0, sp, verf = 0;
	FILE*f = fopen("loto.in", "r"), *g = fopen("loto.out", "w");
	fscanf(f, "%d%d", &n, &s);
	int *v = (int*)malloc(sizeof(int)*n);
	for (i = 0; i < n; i++)
		fscanf(f, "%d", &v[i]);
	for (i = 0; i < n; i++)
	{
		for (j = i; j < n; j++)
		{
			for (k = j; k < n; k++)
			{
				sume[nr].i = i; sume[nr].j = j; sume[nr].k = k;
				sume[nr].val = v[i] + v[j] + v[k];
				nr++;
			}
		}
	}
	std::sort(sume, sume + nr, cmp);
	for (i = 0; i < nr; i++)
	{
		sp = s - sume[i].val;
		verf = cautare(sume, nr, sp);
		if (verf >= 0)
		{
			fprintf(g, "%d %d %d %d %d %d", v[sume[i].i], v[sume[i].j], v[sume[i].k], v[sume[verf].i], v[sume[verf].j], v[sume[verf].k]);
			break;
		}
	}
	if (verf < 0)
		fprintf(g, "%d", -1);
	fclose(f); fclose(g);
	return 0;
}