Pagini recente » Cod sursa (job #2270891) | Cod sursa (job #2665321) | Cod sursa (job #2060975) | Cod sursa (job #2207744) | Cod sursa (job #463019)
Cod sursa(job #463019)
// Davidoaia Bogdan-Mihai 323CA
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct gutuie {
long h; // inaltimea/nivelul gutuii
long w; // greutatea gutuii
};
// compara dupa inaltime (si greutate daca e1.h = e2.h) 2 gutui
int comph(const void *e1, const void *e2) {
struct gutuie *a = (struct gutuie *)e1;
struct gutuie *b = (struct gutuie *)e2;
if(a->h != b->h)
return a->h - b->h;
return b->w - a->w;
}
// interclasare a si b
// intoarce un vector nou
long* merge(long *a, long na, long *b, long nb) {
long *ret = (long *) malloc( (na + nb) * sizeof(long) );
long i = 0, j = 0, k = 0;
while(i < na && j < nb)
if(a[i] > b[j])
ret[k++] = a[i++];
else
ret[k++] = b[j++];
while(i < na)
ret[k++] = a[i++];
while(j < nb)
ret[k++] = b[j++];
return ret;
}
// alegere cele mai grele gutui din prev si crt
// se aleg maxim level+1 gutui
long* best(long *prev, long *nc, long *crt, long nl, long level) {
long *ret;
long i;
if(crt == NULL)
// nivelul curent e null, ramane alegerea precedenta
return prev;
if(prev == NULL) {
// primul nivel nenul, se intoarce acest nivel
ret = (long *) malloc(nl * sizeof(long));
for(i = 0; i < nl; i++)
ret[i] = crt[i];
*nc = nl;
return ret;
}
ret = merge(prev, *nc, crt, nl);
if(*nc + nl < level + 1)
*nc = *nc + nl;
else
*nc = level + 1;
free(prev);
return ret;
}
int main() {
long n, u, h;
long i, j, l, k;
struct gutuie *g;
FILE *in = fopen("gutui.in", "r");
fscanf(in, "%ld%ld%ld", &n, &h, &u);
g = (struct gutuie *) malloc(n * sizeof(struct gutuie));
for( i = 0; i < n; i++)
fscanf(in, "%ld%ld", &(g[i].h), &(g[i].w) );
fclose(in);
for( i = 0; i < n; i++)
if(h < g[i].h)
g[i].h = -1;
else
g[i].h = ceil( (h - g[i].h) / u);
qsort(g, n, sizeof(struct gutuie), comph);
// nlevel = nr de nivele pe care sunt distribuite gutuile
long nlevel = g[n-1].h + 1;
// nl[i] = min (nr de gutui pe nivelul i , i+1), i = 0,nlevel-1
long *nl = (long *) calloc(sizeof(long), nlevel);
// t -> greutatile gutuilor puse pe nivele
long **t = (long **) calloc(sizeof(long), nlevel);
// distribuire pe nivele a gutuilor
i = 0;
while(g[i].h == -1)
i++;
while(i < n) {
l = g[i].h;
j = 0;
while( (g[i].h == l) && j <= l && i < n) {
j++;
i++;
}
nl[l] = j;
t[l] = (long *) malloc (j * sizeof(long));
for(k = 0; k < j; k++)
t[l][k] = g[i-j+k].w;
while(g[i].h == l && i < n)
i++;
}
free(g);
long *choice = NULL;
long nc = 0;
for(l = 0 ; l < nlevel; l++)
choice = best(choice, &nc, t[l], nl[l], l);
FILE *out = fopen("gutui.out", "w");
long s = 0;
for(i = 0; i < nc; i++)
s += choice[i];
fprintf(out, "%ld\n",s);
fclose(out);
if(choice != NULL)
free(choice);
free(nl);
for(i = 0; i < nlevel; i++)
if(t[i] != NULL)
free(t[i]);
free(t);
return 0;
}