Cod sursa(job #189826)

Utilizator stefysStefan stefys Data 18 mai 2008 16:20:27
Problema Loto Scor 45
Compilator c Status done
Runda Arhiva de probleme Marime 2.53 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, complement; /*D2 *valori2;*/
	unsigned int *valori1;
	D3 *findptr;
	unsigned int size3=0;
	unsigned int N, S, i, crt,j, gasitsol=0;
	unsigned int n1,n2,n3;
	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(unsigned int)*N);
	for (i=0; i<N; ++i) {
		scanf("%u ", &crt);
		valori1[i] = 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;
		}*/
	}
	for (n1=0; n1<N; ++n1)
		for (n2=n1; n2<N; ++n2)
			for (n3=n2; n3<N; ++n3) {
				valori3[size3].suma = valori1[n1]+valori1[n2]+valori1[n3];
				if (valori3[size3].suma < S) {
					valori3[size3].v1 = valori1[n1];
					valori3[size3].v2 = valori1[n2];
					valori3[size3++].v3 = valori1[n3];
				}
			}
	//printf("%u %u %u\n",size1,size2,size3);

	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+1)/2 && !gasitsol; ++i) {
		if (valori3[i].suma > S) continue;
		complement.suma = S - valori3[i].suma;
		if ( (findptr = (const D3*)bsearch((const D3*)&complement, valori3, size3, sizeof(D3), sortfunc)) != 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;
}