Cod sursa(job #435042)

Utilizator adrian.lunguLungu Adrian adrian.lungu Data 6 aprilie 2010 20:26:30
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 7.06 kb
#include <stdio.h>
#include <stdlib.h>

#define true 1
#define false 0

typedef struct Node{
      int h,w;
      struct Node *next;
      unsigned char noOfElements;
} node;

typedef node* linkedList;

typedef struct bNode{
      int h,w;
      struct bNode * left, * right;
} BNode;

typedef struct {
      BNode *nodes;
      unsigned char noOfNodes;
} BTree;


void merge(int *h, int *w, int s, int m, int d) {
      int i = s;
      int j = m + 1;
      int k = 0;
      int h2[100000];
      int w2[100000];
      
      while (i <= m && j <= d) {
	    if (w[i] < w[j]) {
		  h2[k] = h[i];
		  w2[k++] = w[i++];
	    }
	    else { 
		  h2[k] = h[j];
		  w2[k++] = w[j++];
	    }
      }
      for (; i <= m ; i++){
	    h2[k] = h[i];
	    w2[k++] = w[i];
      }
      for (;j <= d ; j++){ 
	    h2[k] = h[j];
	    w2[k++] = w[j];
      }
      
      for (i = 0 ; i <= (d-s) ; i++){
	    w[i+s] = w2[i];
	    h[i+s] = h2[i];
      }
}

void mSort(int *h, int *w, int s, int d) {
      if (s < d) {
	    int m = (s+d)/2;
	    mSort(h,w,s,m);
	    mSort(h,w,m+1,d);
	    merge(h,w,s,m,d);
      }
}

BNode *newBNode(int h, int w) {
      BNode *aBNode = (BNode*)malloc(sizeof(BNode));
      aBNode -> left = NULL;
      aBNode -> right = NULL;
      aBNode -> h = h;
      aBNode -> w = w;
      return aBNode;
}

void add(BTree *aBTree, BNode *aBNode) {
      BNode *tempBNode = aBTree -> nodes;
      while (tempBNode != NULL) { // nu este frunza;
	    if (tempBNode -> w > aBNode -> w) {
		  if (tempBNode -> left != NULL) {
			tempBNode = tempBNode -> left;
		  }
		  else {	// insert in left
			tempBNode -> left = aBNode;
			return;
		  }
	    }
	    else { 
		  if (tempBNode -> right != NULL) {
			tempBNode = tempBNode -> right;
		  }
		  else {	// insert in right;
			tempBNode -> right = aBNode;
			return;
		  }
	    }
      }
      aBTree -> nodes = aBNode;
}

void delMin(BTree *aBTree){
      BNode *tempBNode = aBTree -> nodes;
      BNode *parentBNode = NULL;
      while (tempBNode != NULL) {
	    if (tempBNode -> left != NULL) {
		  parentBNode = tempBNode;
		  tempBNode = tempBNode -> left;
	    }
	    else {
		  if (parentBNode != NULL) {
			parentBNode -> left = tempBNode -> right;
			return;
		  }
		  else {
			aBTree -> nodes = tempBNode -> right;
			return;
		  }
	    }
      }
}

void printBTree(BNode *aBNode) {
      if (aBNode != NULL) {
	    if (aBNode -> left != NULL)
		  printBTree (aBNode -> left);
	    printf("%d(%d) ",aBNode -> h, aBNode -> w);
	    if (aBNode -> right != NULL)
		  printBTree (aBNode -> right);
      }
}

void countValues(BNode *aBNode, unsigned long long *suma) {
      if (aBNode != NULL) {
	    if (aBNode -> left != NULL)
		  countValues (aBNode -> left, suma);
	    *suma += aBNode -> w;
	    //printf("%d(%d) ",aBNode -> h, aBNode -> w);
	    //printf("suma = %lld ", *suma);
	    if (aBNode -> right != NULL)
		  countValues (aBNode -> right, suma);
      }
}

node* newNode (int h, int w, node *nextNode){
      node *aNode = (node*)malloc(sizeof(node));
      aNode -> h = h;
      aNode -> w = w;
      aNode -> next = nextNode;
      aNode -> noOfElements = 0;
      return aNode;
}

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

int listInsertAsc(linkedList aList, int maxEl, node *aNode) {
      node * tempNode = aList;
      while (tempNode -> next != NULL && tempNode -> next -> w < aNode -> w) {
	    tempNode = tempNode -> next;
      }
      setNext(aNode,tempNode->next);
      setNext(tempNode,aNode);
      return true;
}

int listInsertDesc(linkedList aList, int maxEl, node *aNode) {
      node * tempNode = aList;
      int listCount = 0;
      while (tempNode -> next != NULL && tempNode -> next -> w > aNode -> w && listCount < maxEl) {
	    tempNode = tempNode -> next;
	    listCount ++;
      }
      if (listCount == maxEl)
	    return false;
      setNext(aNode,tempNode->next);
      setNext(tempNode,aNode);
      return true;
}

int isEmpty(linkedList aList){
      if (aList -> next == NULL)
	    return true;
      return false;
}

node *getNextNode(linkedList aList){
      node * tempNode = aList -> next;
      aList -> next = aList -> next -> next;
      return tempNode;
}

void printList(linkedList aList) {
      node * tempNode = aList -> next;
      while (tempNode != NULL){
	    printf("%d %d\n",tempNode -> h, tempNode -> w);
	    tempNode = tempNode ->next;
      }
}

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;
      
      int *h = (int*)malloc(N*sizeof(int));
      int *w = (int*)malloc(N*sizeof(int));
      
      // Read elements 
      for (i = 0 ; i < N ; i++) {
	    fscanf(fin,"%d %d", &h[i], &w[i]);
      }
      
      // Sort elements
      mSort(h,w,0,N-1);
  
      // Make list of lists
      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 - h[i])/U;
	    //if (lists[listNo] -> noOfElements < (listNo + 1)) {
		  listInsertDesc(lists[listNo],N,newNode(h[i],w[i],NULL));
		//  lists[listNo] -> noOfElements++;
	    //}
      }
      
/*
      // print lists
      for (i = 0 ; i < noOfLists ; i++) {
	    printf("lista %d:\n",i);
		  printList(lists[i]);
      }
*/

      //linkedList selected = (linkedList) malloc (sizeof(node));
      
      free(h);
      free(w);
      
      BTree * aBTree = (BTree*) malloc(sizeof(BTree));
      aBTree -> nodes = NULL;
      
      int listCount = 0;
      for (i = 0 ; i < noOfLists ; i++) {
	    while (isEmpty(lists[i]) == false) {
		  //listInsertAsc(selected,i + 1,getNextNode(lists[i]));
		  node *tempNode = getNextNode(lists[i]);
		  add(aBTree,newBNode(tempNode -> h,tempNode -> w));
		  listCount ++;
		  //printf("Lista dupa inserare: \n");
		  //printList(selected);
		  if (listCount > i + 1) {
			delMin(aBTree);
		//	printf("pas = %d, dim lista = %d, Lista dupa stergere: \n",i + 1,listCount);
		//	printList(selected);
			listCount --;
		  }
	    }
      }
      
      
      /*add(aBTree,newBNode(100,10));
      add(aBTree,newBNode(200,20));
      add(aBTree,newBNode(10,15));
      add(aBTree,newBNode(250,25));
      add(aBTree,newBNode(10,30));
      add(aBTree,newBNode(250,24));
      printBTree(aBTree -> nodes);
      delMin(aBTree);
      printf("\n");
      printBTree(aBTree -> nodes);*/
     // printBTree(aBTree -> nodes);

      //printf("lista finala:\n");
      //printList(selected);
      unsigned long long suma = 0;
      //while (isEmpty(selected) == false) {
	    //node *tempNode = getNextNode(selected);
	    countValues(aBTree -> nodes, &suma);
	    //suma += tempNode -> w;
	//    printf("%d %d\n",tempNode -> h,tempNode -> w);
      //}
      
      //printBTree(aBTree->nodes);
      
      fprintf(fout,"%lld\n",suma);
      //printf("%lld\n",suma);
      fclose(fin);
      fclose(fout);
      return 0;
}