Pagini recente » Cod sursa (job #794809) | Istoria paginii runda/cerculdeinfo-lectia6-arbori/clasament | Cod sursa (job #1697224) | Cod sursa (job #1896327) | Cod sursa (job #435461)
Cod sursa(job #435461)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
typedef struct {
unsigned int ht;
unsigned int g;
int ns;
}elem;
int comp(const void *a, const void *b){
elem *p1 = (elem*)a;
elem *p2 = (elem*)b;
if (p1->g < p2->g)
return 1;
if (p1->g > p2->g)
return -1;
return 0;
}
int main(){
unsigned int n,h,u;
int i,j;
elem *gutui, *p;
char *secv;
int two[32];
int logr,expr;
int g = 0;
FILE *fin = fopen("gutui.in", "r");
fscanf(fin,"%d %d %d",&n,&h,&u);
gutui = (elem*)malloc(n * sizeof(elem));
for (p = gutui, i = 0; i < n; i++, p++){
fscanf(fin,"%d %d", &(p->ht), &(p->g));
p->ns = (h - p->ht) / u + 1;
}
fclose(fin);
qsort(gutui, n, sizeof(elem),comp);
secv = (char*)malloc((n + 1) * sizeof(char));
memset(secv, 0, (n + 1) * sizeof(char));
memset(two,0,32 * sizeof(int));
/* for (p = gutui, i = 0; i < n; i++, p++)
printf("(%d, %d) ",p->g, p->ns);
printf("\n");*/
for (p = gutui, i = 0; i < n; i++, p++){
for (j = p->ns; j > 0 && *(secv + j) == 1; j--);
if (j > 0){
*(secv + j) = 1;
g += p->g;
}
}
/* for (p = gutui, i = 0; i < n; i++, p++){
if (p->ns >= n)// poate fi ultima gutuie luata
g += p->g;
else{
logr = (ceil(log((double)p->ns)));
if (p->ns > 1 << logr)
logr++;
if (logr > 0){//nu este prima gutuie care trebuie luata
for (expr = 1 << (logr - 1), j = p->ns; j > expr; j--)//verifica pe intervalul ([log p->ns],p->ns)
if (*(secv + j) == 0){
*(secv + j) = 1;
two[logr]++;
g += p->g;
break;
}
if (j == expr){//nu a reusit sa insereze in intervalul precedent
for (logr--; logr >= 0 && two[logr] == ((logr != 0)?(1 << (logr - 1)):1); logr--);//cauta primul interval cu elemente libere
if (logr >= 0){//a gasit un interval cu elemente libere
for (j = 1 << logr; j > ((logr != 0)?(1 << (logr - 1)):0) && *(secv + j) == 1; j--);//cauta primul element liber
*(secv + j) = 1;
two[logr]++;
g += p->g;
}
}
}
else//este prima gutuie care trebuie luata
if (*(secv + 1) == 0){//verifica daca poate fi luata prima
*(secv + 1) = 1;
two[0]++;
g += p->g;
}
}
for (j = 0; j < n; j++)
printf("%d ",*(secv + j));
printf("\n");
}*/
free(secv);
free(gutui);
FILE *fout = fopen("gutui.out", "w");
fprintf(fout, "%d\n", g);
fclose(fout);
return 0;
}