Cod sursa(job #189818)

Utilizator stefysStefan stefys Data 18 mai 2008 15:51:11
Problema Loto Scor 25
Compilator c Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct D3 {
	unsigned int suma, v1, v2, v3;
} D3;

typedef struct D2 { unsigned int v1,v2; } D2;
typedef struct D1 { unsigned int v1; } D1;

int sortfunc (const void *v1, const void *v2)
{
	const D3 *v1c = (const D3 *)v1;
	const D3 *v2c = (const D3 *)v2;
	if (v1c->suma < v2c->suma)
		return -1;
	else if (v1c->suma == v2c->suma)
		return 0;
	else
		return 1;
}

D3 *bfind (D3 *v, unsigned int size, unsigned int tofind)
{
	unsigned int start=0, end=size-1, median;
	while (start < end) {
		median = (start+end)/2;
		if (v[median].suma == tofind) return v+median;
		else if (v[median].suma < tofind) start=median+1;
		else end=median-1;
	}
	if (v[start].suma == tofind) return v+start;
	return NULL;
}

int main (void)
{
	D3 *valori3; D2 *valori2; D1 *valori1;
	D3 *findptr;
	unsigned int size1=0,size2=0,size3=0, complement;
	unsigned int N, S, i, crt,j, gasitsol=0;
	freopen("loto.in", "r", stdin);
	freopen("loto.out", "w+", stdout);
	
	scanf("%u %u\n", &N, &S);
	valori3 = malloc(sizeof(D3)*N*N*N);
	valori2 = malloc(sizeof(D2)*N*N);
	valori1 = malloc(sizeof(D1)*N);
	for (i=0; i<N; ++i) {
		scanf("%u ", &crt);
		valori1[size1++].v1 = crt;
		for (j=0; j<size1; ++j) {
			valori2[size2].v1 = valori1[j].v1;
			valori2[size2++].v2 = crt;
		}
		for (j=0; j<size2; ++j) {
			valori3[size3].v1   = valori2[j].v1;
			valori3[size3].v2   = valori2[j].v2;
			valori3[size3].v3   = crt;
			valori3[size3++].suma = valori2[j].v1+valori2[j].v2+crt;
		}
	}
	/*printf("%u %u %u\n",size1,size2,size3);
	for (i=0; i<size3; ++i) {
		printf("valori3[%u] = %u\n",i,valori3[i]);
	}*/
	qsort((void*)valori3, size3, sizeof(D3), sortfunc);
	/*for (i=0; i<size3; ++i) {
		printf("valori3[%u] = %u\n",i,valori3[i]);
	}*/
	
	for (i=0; i<size3/2 && !gasitsol; ++i) {
		if (valori3[i].suma > S) continue;
		complement = S - valori3[i].suma;
		if ( (findptr = bfind(valori3, size3, complement)) != NULL) {
			printf("%u %u %u %u %u %u\n",
				valori3[i].v1, valori3[i].v2, valori3[i].v3,
				findptr->v1, findptr->v2, findptr->v3
			);
			gasitsol = 1;
		}
	}
	if (!gasitsol) printf("-1\n");
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}