Cod sursa(job #432979)

Utilizator adrian.lunguLungu Adrian adrian.lungu Data 3 aprilie 2010 01:20:29
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 3.33 kb
#include <stdio.h>
#include <stdlib.h>

#define true 1
#define false 0

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

typedef node* linkedList;

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

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

int listInsertAsc(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 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;
}

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);
      //printf("%d %d %d\n",N,H,U);
      int i;
      // Make list of lists
      int noOfLists = H/U;
      if (H/U) noOfLists++;
      linkedList *lists = (linkedList*) malloc (noOfLists * sizeof(linkedList));
      //linkedList lists[100];
      for (i = 0 ; i < noOfLists ; i++) {
	    lists[i] = (linkedList) malloc(sizeof(node));
      }
      
      //listInsert(lists[0],N,newNode(4,10,NULL));
      //printf("%d %d\n",lists[0] -> next -> w, lists[0] -> next -> h);
      // Read elements and fill the lists
      for (i = 0 ; i < N ; i++) {
	    int h, w, listNo;
	    fscanf(fin,"%d %d",&h, &w);
	    listNo = (H - h)/U;
	    //printf("%d %d %d\n",h,w,listNo);
	    listInsertAsc(lists[listNo],N,newNode(h,w,NULL));
      }
      /*
      // print lists
      for (i = 0 ; i < noOfLists ; i++) {
	    printf("lista %d:\n",i);
	    while (isEmpty(lists[i]) == false) {
		  node * tempNode = getNextNode(lists[i]);
		  int h = tempNode -> h;
		  int w = tempNode -> w;
		  printf ("%d %d\n",h, w);
	    }
	    printf("\n");
      }*/
      
      linkedList selected = (linkedList) malloc (sizeof(node));
      
      int listCount = 0;
      for (i = 0 ; i < noOfLists ; i++) {
	    int inserted = true;
	    while (isEmpty(lists[i]) == false && inserted == true) {
		  inserted = listInsertDesc(selected,i + 1,getNextNode(lists[i]));
		  listCount += inserted;
		  if (listCount > i + 1) {
			getNextNode(selected);
			listCount --;
		  }
	    }
      }
      
      
      unsigned long long suma = 0;
      while (isEmpty(selected) == false)
	    suma += getNextNode(selected) -> w;
      fprintf(fout,"%lld\n",suma);
      fclose(fin);
      fclose(fout);
      return 0;
}