Pagini recente » Cod sursa (job #784475) | Cod sursa (job #1873222) | Cod sursa (job #2306049) | Cod sursa (job #917961) | Cod sursa (job #189818)
Cod sursa(job #189818)
#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;
}