Advertisement
Guest User

CH4 Tasks

a guest
Jun 20th, 2011
1,465
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 3.11 KB | None | 0 0
  1.  
  2. /*
  3.  * Tuenti Contest
  4.  * Challenge 4 - Task Durations
  5.  * Author: Pedro Antonio Pardal Jimena
  6.  * Email: pardal@alu.uma.es
  7.  */
  8.  
  9. #include <stdio.h>
  10. #include <stdlib.h>
  11. #include <string.h>
  12.  
  13. #define IN_FILENAME "in"
  14. #define BUFFER_SIZE 0x1000
  15.  
  16. struct node
  17. {
  18.     unsigned int cost, child, brother;
  19. };
  20.  
  21. struct node_search
  22. {
  23.     unsigned int tid, cost;
  24. };
  25.  
  26. int total;
  27. struct node *table;
  28.  
  29. int stack_ptr = 0;
  30. struct node_search *stack;
  31.  
  32. #define stack_empty !stack_ptr
  33.  
  34. static inline void stack_push(struct node_search nod)
  35. {
  36.     stack[stack_ptr++] = nod;
  37. }
  38.  
  39. static inline struct node_search stack_pop()
  40. {
  41.     return stack[--stack_ptr];
  42. }
  43.  
  44. char buffer[BUFFER_SIZE];
  45.  
  46. static void read_table()
  47. {
  48.     int i, tid, cost, depends, brother;
  49.     char *tok;
  50.     FILE *in;
  51.    
  52.     in = fopen(IN_FILENAME, "r");
  53.    
  54.     if (in == NULL)
  55.     {
  56.         perror("fopen");
  57.         exit(-1);
  58.     }
  59.    
  60.     while (fgets(buffer, BUFFER_SIZE, in) != NULL)
  61.     {
  62.         if (buffer[0] != '#' && buffer[0] != '\0' && buffer[0] != '\n')
  63.         {
  64.             total = atoi(buffer);
  65.             table = (struct node *) malloc(total*sizeof(struct node));
  66.             stack = (struct node_search *) malloc(total*sizeof(struct node_search));
  67.  
  68.             break;
  69.         }
  70.     }
  71.    
  72.     for (i = 0; i < total; i++)
  73.     {
  74.         if (fgets(buffer, BUFFER_SIZE, in) == NULL)
  75.         {
  76.             perror("fgets");
  77.             exit(-1);
  78.         }
  79.    
  80.         if (buffer[0] == '#' || buffer[0] == '\0' || buffer[0] == '\n')
  81.         {
  82.             i--;
  83.             continue;
  84.         }
  85.        
  86.         tok = strtok(buffer, ",\n");
  87.         tid = atoi(tok);
  88.         tok = strtok(NULL, ",\n");
  89.         cost = atoi(tok);
  90.        
  91.         table[tid].cost = cost;
  92.         table[tid].child = -1;
  93.         table[tid].brother = -1;
  94.     }
  95.    
  96.     while (fgets(buffer, BUFFER_SIZE, in) != NULL)
  97.     {
  98.         if (buffer[0] != '#' && buffer[0] != '\0' && buffer[0] != '\n')
  99.         {
  100.             tok = strtok(buffer, ",\n");
  101.             tid = atoi(tok);
  102.            
  103.             brother = -1;
  104.            
  105.             while ((tok = strtok(NULL, ",\n")) != NULL)
  106.             {              
  107.                 depends = atoi(tok);
  108.                 table[depends].brother = brother;
  109.                 brother = depends;
  110.             }
  111.            
  112.             table[tid].child = brother;
  113.         }
  114.     }
  115.  
  116.     fclose(in);
  117. }
  118.  
  119. static void print_table()
  120. {
  121.     int i;
  122.  
  123.     for (i = 0; i < total; i++)
  124.     {
  125.         printf("Task %d: Cost->%d, Child->%d, Brother->%d\n",
  126.                 i, table[i].cost, table[i].child, table[i].brother);
  127.     }
  128. }
  129.  
  130. static int compute_cost(int tid)
  131. {
  132.     struct node_search nod = {.tid = tid, .cost = table[tid].cost};
  133.     int maxcost = -1, childcost = -1, child = -1;
  134.  
  135.     stack_push(nod);
  136.    
  137.     while (!stack_empty)
  138.     {
  139.         nod = stack_pop();
  140.  
  141.         childcost = nod.cost;
  142.        
  143.         if (childcost > maxcost)
  144.             maxcost = childcost;
  145.  
  146.         child = table[nod.tid].child;
  147.                
  148.         while (child != -1)
  149.         {
  150.             nod.tid = child;
  151.             nod.cost = table[child].cost + childcost;
  152.            
  153.             stack_push(nod);
  154.            
  155.             child = table[child].brother;
  156.         }
  157.     }
  158.    
  159.     return maxcost;
  160. }
  161.  
  162. int main(int argc, char *argv[])
  163. {
  164.     char *tok;
  165.     int tid, cost;
  166.  
  167.     read_table();
  168.        
  169.     if (fgets(buffer, BUFFER_SIZE, stdin) == NULL)
  170.     {
  171.         perror("fgets");
  172.         exit(-1);
  173.     }
  174.    
  175.     tok = strtok(buffer, ",\n");
  176.    
  177.     do
  178.     {
  179.         tid = atoi(tok);
  180.         cost = compute_cost(tid);
  181.        
  182.         fprintf(stdout, "%d %d\n", tid, cost);
  183.     }
  184.     while ((tok = strtok(NULL, ",\n")) != NULL);
  185.    
  186.     return 0;
  187. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement