Cod sursa(job #441897)

Utilizator adrian.nedeleaNedelea Adrian adrian.nedelea Data 13 aprilie 2010 17:31:45
Problema Gutui Scor 20
Compilator c Status done
Runda teme_upb Marime 3.55 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct {
	int h, w;
}	gutui;

struct HeapStruct {
    int Capacity;
    int Size;
    gutui *Elements;
};

typedef struct HeapStruct *Heap;

int N,H,U;

Heap Initialize(int MaxElements) {
    Heap H;

     H = (Heap) malloc (sizeof(struct HeapStruct));
     H->Elements = (gutui*) malloc ((MaxElements + 1) * sizeof(gutui));

     H->Capacity = MaxElements;
     H->Size = 0;
     (H->Elements[0]).w = 30000;

     return H;
}

void MakeEmpty(Heap H) {
    H->Size = 0;
}

/* H->Element[ 0 ] is a sentinel */
int isEmpty(Heap H) {
    return H->Size == 0;
}

int IsFull(Heap H) {
    return H->Size == H->Capacity;
}

void Insert(gutui X, Heap H) {
    int i;

    for (i = ++H->Size; H->Elements[i/2].w < X.w; i /= 2)
        H->Elements[i] = H->Elements[i/2];
    H->Elements[i] = X;
}


gutui DeleteMax(Heap H) {
    int i, Child;
    gutui MaxElement, LastElement;

    if (isEmpty(H)) 
    	return H->Elements[0];

     MaxElement = H->Elements[1];
     LastElement = H->Elements[H->Size--];

     for (i = 1; i * 2 <= H->Size; i = Child) {
        /* Find smaller child */
    	 Child = i * 2;
         if (Child != H->Size && (H->Elements[Child+1]).w > (H->Elements[ Child ]).w)
             Child++;

        /* Percolate one level */
         if (LastElement.w < (H->Elements[Child]).w)
             H->Elements[ i ] = H->Elements[ Child ];
        else
             break;
    }
     H->Elements[ i ] = LastElement;
     return MaxElement;
}

gutui FindMax(Heap H) {
    //if (!isEmpty(H))
        return H->Elements[1];
   
    //return H->Elements[0];
}

void Destroy(Heap H) {
    free(H->Elements);
    free(H);
}

void afisare(Heap H, FILE *out) {
	int i;
	for (i=0; i<H->Size; i++)
		fprintf(out,"%d %d\n",H->Elements[i].h, H->Elements[i].w);
	fprintf(out,"\n");
}

int compare (const void * a, const void * b) {
  	return ( ((*(gutui*)b).h)/U - ((*(gutui*)a).h)/U );
}

int max(int x, int y) {
	return x>y?x:y;
}

int main() {

	int i;
	char c;

	FILE *in = fopen("gutui.in","r");
	FILE *out = fopen("gutui.out","w");

	fscanf(in,"%d%d%d%c",&N,&H,&U,&c);	
	gutui g[N];

	for (i=0; i<N; i++) 
		fscanf(in,"%d%d%c",&g[i].h,&g[i].w,&c);	
	
	qsort (g, N, sizeof(gutui), compare);

	int greutate_totala = 0;
	int offset = U - H % U;
  	if (offset == U) offset = 0;
  	int top = offset - U;
	int last = N-1;

	if (U == 0) {
		for (i=0; i<N; i++)
			greutate_totala += g[i].w;
		fprintf(out,"%d\n",greutate_totala);
		return 0;
	}

	Heap hp = Initialize(N);

	while ( ( last >=0  || !isEmpty(hp) ) && top <= H) {
		if (!isEmpty(hp)) {
			greutate_totala += FindMax(hp).w;
			DeleteMax(hp);

			top += U;
		}

		else {/*
			if(offset) {
				top += U * max(1, (g[last].h - top + offset) / U) - offset;
				offset = 0;
			}
			else */
				top += U * max(1, (g[last].h - top) / U);
		}

		while (last >=0 && g[last].h <= top) {
			Insert(g[last],hp);
			last--;
		}
	}

	fprintf(out,"%d",greutate_totala);


/*
	while ((apples.size() or available_weights.size()) and top <= H) {
    if (available_weights.size()) {
      picked_weight += available_weights.front();
      std::pop_heap(available_weights.begin(), available_weights.end());
      available_weights.pop_back();
      top += U;
    }
    else {
      top += U * std::max(1, (apples.back().h - top) / U);
    }

    while (apples.size() and apples.back().h <= top) {
      available_weights.push_back(apples.back().w);
      std::push_heap(available_weights.begin(), available_weights.end());
      apples.pop_back();
    }
  }

  return picked_weight;
}
*/
	
	fclose(in);
	fclose(out);
	Destroy(hp);

	return 0;
}