Cod sursa(job #435815)

Utilizator adrian.lunguLungu Adrian adrian.lungu Data 7 aprilie 2010 21:24:10
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 4.64 kb
#include <stdio.h>
#include <stdlib.h>
#include <values.h>

#define true 1
#define false 0
#define MinData -1

typedef struct gutuie {
      int w;
      int h;
} Gutuie;

typedef struct Node{
      Gutuie g;
      struct Node *next;
      unsigned char noOfElements;
} node;

typedef node* linkedList;

typedef struct heapStruct {
      int Capacity;
      int Size;
      Gutuie *Gutui;
} HeapStruct;

typedef HeapStruct* PriorityQueue;

// Mergesort
void merge(Gutuie * v, int s, int m, int d) {
      int i = s;
      int j = m + 1;
      int k = 0;
      Gutuie v2[100000];
      
      while (i <= m && j <= d) {
	    if (v[i].w < v[j].w) {
		  v2[k++] = v[i++];
	    }
	    else {
		  v2[k++] = v[j++];
	    }
      }
      for (; i <= m ; i++){
	    v2[k++] = v[i];
      }
      for (;j <= d ; j++){
	    v2[k++] = v[j];
      }
      
      for (i = 0 ; i <= (d-s) ; i++){
	    v[i+s] = v2[i];
      }
}

void mSort(Gutuie * v, int s, int d) {
      if (s < d) {
	    int m = (s+d)/2;
	    mSort(v,s,m);
	    mSort(v,m+1,d);
	    merge(v,s,m,d);
      }
}
// End of Mergesort

// PriorityQueue builder
PriorityQueue MakeQueue(int MaxCapacity) {
      PriorityQueue Q = (PriorityQueue)malloc(sizeof(HeapStruct));
      Q -> Capacity = MaxCapacity;
      Q -> Size = 0;
      Q -> Gutui = (Gutuie*)malloc(MaxCapacity*sizeof(Gutuie));
      Q -> Gutui[0].w = MinData;
      Q -> Gutui[0].h = MinData;
      return Q;
}

// Insert an element in a Priority Queue
void Insert(Gutuie oGutuie, PriorityQueue Q) {
      int i;
      for (i = ++ Q -> Size ; Q -> Gutui[i / 2].w > oGutuie.w ; i /= 2)
	    Q -> Gutui [i] = Q -> Gutui [i / 2];
      Q -> Gutui [i] = oGutuie;
}

// Delete the first element from a Priority Queue
Gutuie DeleteMin(PriorityQueue Q) {
      int i, Child;
      Gutuie MinElement, LastElement;
      
      MinElement = Q -> Gutui[1];
      LastElement = Q -> Gutui[Q -> Size --];
      
      for (i = 1; i * 2 <= Q->Size; i = Child) {
	    Child = i * 2;
	    if (Child != Q -> Size && Q -> Gutui[Child + 1].w < Q -> Gutui[Child].w)
		  Child++;
	    if (LastElement.w > Q -> Gutui[Child].w)
		  Q -> Gutui[i] = Q -> Gutui[Child];
	    else break;
      }
      Q -> Gutui [i] = LastElement;
      return MinElement;
}

// Check if the Priority Queue is empty
int IsEmpty(PriorityQueue Q) {
      if (Q -> Size == 0)
	    return 1;
      return 0;
}

// Node builder
node* newNode (Gutuie oGutuie, node *nextNode){
      node *aNode = (node*)malloc(sizeof(node));
      aNode -> g = oGutuie;
      aNode -> next = nextNode;
      aNode -> noOfElements = 0;
      return aNode;
}

void setNext(node *aNode, node* nextNode){
      aNode -> next = nextNode;
}

// Insert an elemnt in a list
void listInsertFront(linkedList aList, node *aNode) {
      node * tempNode = aList;
      setNext(aNode,tempNode->next);
      setNext(tempNode,aNode);
}

// Check if the list is empty
int isEmpty(linkedList aList){
      if (aList -> next == NULL)
	    return true;
      return false;
}

// Delete and return the first element from the list
Gutuie getNextNode(linkedList aList){
      node * tempNode = aList -> next;
      aList -> next = aList -> next -> next;
      return tempNode -> g;
}

int main() {
      
      FILE *fin, *fout;
      int N, H, U;
      fin = fopen("gutui.in","r");
      fout = fopen("gutui.out","w");
      fscanf(fin,"%d %d %d", &N, &H, &U);
      int i;
      
      Gutuie *v = (Gutuie*)malloc(N*sizeof(Gutuie));
      
      // Read elements 
      for (i = 0 ; i < N ; i++) {
	    fscanf(fin,"%d %d", &v[i].h, &v[i].w);
      }
      
      // Sort elements
      mSort(v,0,N-1);
  
      // Make list of lists (intervals)
      int noOfLists = H/U;
      if (H % U) noOfLists++;
      linkedList *lists = (linkedList*) malloc (noOfLists * sizeof(linkedList));
      for (i = 0 ; i < noOfLists ; i++) {
	    lists[i] = (linkedList) malloc(sizeof(node));
	    lists[i] -> noOfElements = 0;
      }
      
      // Fill the lists
      for (i = 0 ; i < N ; i++) {
	    int listNo;
	    listNo = (H - v[i].h)/U;
	    listInsertFront(lists[listNo],newNode(v[i],NULL));
	}
      
      free(v);
      
      // Select the best elements
      PriorityQueue Q = MakeQueue(H / U + 1);
      for (i = 0 ; i < noOfLists ; i++) {
	    while (isEmpty(lists[i]) == false) {
		  Gutuie oGutuie = getNextNode(lists[i]);
		  if (Q -> Size == (i + 1) && Q -> Gutui[1].w > oGutuie.w)
			continue;
		  else Insert(oGutuie, Q);
		  if (Q -> Size > i + 1)
			DeleteMin(Q);
	    }
      }
      
      unsigned long long suma = 0;
      while (IsEmpty(Q) == 0) {
	    Gutuie x = DeleteMin(Q);
	    suma += x.w;
      }
      
      fprintf(fout,"%lld\n",suma);
      fclose(fin);
      fclose(fout);
      return 0;
}