Computer Programming Contest Preparation

ToolBox - Source for: 103/10305/judged.c



/home/toolbox/public_html/solutions/103/10305/judged.c
    1 #include <stdio.h>
    2 #include <string.h>
    3 #include <sys/types.h>
    4 #include <sys/stat.h>
    5 #include <fcntl.h>
    6 #include <stdint.h>
    7 #include <math.h>
    8 #include <stdlib.h>
    9 #include <ctype.h>
   10 
   11 #define TRUE  (1 == 1)
   12 #define FALSE (1 != 1)
   13 
   14 #define DEBUG if (FALSE)
   15 
   16 /*
   17  *  Author: Isaac Traxler
   18  *    Date: 20210901
   19  * Purpose: fun
   20  * Problem: 10305 - Ordering Tasks
   21  */
   22 
   23 #define MAX_TASKS 105
   24 #define PRINTED -1
   25 
   26 int tasks[MAX_TASKS][MAX_TASKS];
   27 /* a 1 in a column indicates that the task comes before that task
   28  * the 0th column is a count of dependencies
   29  */
   30 int n; /* number of tasks */
   31 int m; /* number of relationships */
   32 
   33 /*
   34  * This template reads data until a terminating value is reached.
   35  */
   36 
   37 void init()
   38 {
   39     /* FUNCTION init */
   40 } /* FUNCTION init */
   41 
   42 void dump()
   43 {
   44     /* FUNCTION dump */
   45     int i;
   46     int j;
   47 
   48     printf("%d tasks with %d relationships\n", n, m);
   49     for (i=1; i<=n; i++)
   50         {
   51             /* for each task */
   52             printf("%3d(%2d): ", i, tasks[i][0]);
   53             for (j=1; j<=n; j++)
   54                 {
   55                     /* for each task */
   56                     printf("%2d ", tasks[i][j]);
   57                 } /* for each task */
   58             printf("\n");
   59         } /* for each task */
   60     printf("\n");
   61 } /* FUNCTION dump */
   62 
   63 int getInput()
   64 {
   65     /* FUNCTION getInput */
   66     int dataReadFlag;
   67     int i;
   68     int j;
   69     int bef;
   70     int aft;
   71 
   72     scanf(" %d %d ", &n, &m);
   73     dataReadFlag = (0 != m) || (0 != n);
   74     if (dataReadFlag)
   75         {
   76             /* initialize task list */
   77             for (i=0; n>=i; i++)
   78                 {
   79                     /* for each task */
   80                     tasks[i][0] = 0;
   81                     for (j=1; n>=j; j++)
   82                         {
   83                             /* for each possible precursor */
   84                             tasks[i][j] = 0;
   85                         } /* for each possible precursor */
   86                 } /* for each task */
   87         } /* initialize task list */
   88     DEBUG dump();
   89     for (i=0; i<m; i++)
   90         {
   91             /* for each relationship */
   92             scanf(" %d %d ", &bef, &aft);
   93             if (0 == tasks[aft][bef])
   94                 {
   95                     /* not set before */
   96                     tasks[aft][bef] = 1;
   97                     tasks[aft][0] = tasks[aft][0] + 1;
   98                     DEBUG printf("(bef %d) (aft %d)\n", bef, aft);
   99                     DEBUG dump();
  100                 } /* not set before */
  101         } /* for each relationship */
  102     return (dataReadFlag);
  103 } /* FUNCTION getInput */
  104 
  105 void rst(int x)
  106 {
  107     /* FUNCTION rst */
  108     int i;
  109 
  110     for (i=1; n>=i; i++)
  111         {
  112             /* for each possible task */
  113             if (0 != tasks[i][x])
  114                 {
  115                     /* found a prereq */
  116                     tasks[i][x] = 0;
  117                     if (0 < tasks[i][0])
  118                         {
  119                             /* decrease couont */
  120                             tasks[i][0] = tasks[i][0] - 1;
  121                         } /* decrease couont */
  122                 } /* found a prereq */
  123         } /* for each possible task */
  124     tasks[x][0] = PRINTED;
  125 } /* FUNCTION rst */
  126 
  127 int noPrereq(int x)
  128 {
  129     /* FUNCTION noPrereq */
  130     return (0 == tasks[x][0]);
  131 } /* FUNCTION noPrereq */
  132 
  133 int notPrinted(int x)
  134 {
  135     /* FUNCTION notPrinted */
  136     return (PRINTED <= tasks[x][0]);
  137 } /* FUNCTION notPrinted */
  138 
  139 int notAllPrinted()
  140 {
  141     /* FUNCTION notAllPrinted */
  142     int i;
  143     int tmp = TRUE;
  144 
  145     for (i=1; n>=i; i++)
  146         {
  147             /* for */
  148             DEBUG printf("tasks[%d][0] = %d\n", i, tasks[i][0]);
  149             tmp = tmp && (PRINTED == tasks[i][0]);
  150         } /* for */
  151     return (! tmp);
  152 } /* FUNCTION notAllPrinted */
  153 
  154 void process()
  155 {
  156     /* FUNCTION process */
  157     int i;
  158     int j;
  159     int first = TRUE;
  160 
  161     DEBUG dump();
  162     while (notAllPrinted())
  163         {
  164             /* while */
  165             DEBUG printf("in while loop\n");
  166             for (i=1; n>=i; i++)
  167                 {
  168                     /* for each task */
  169                     DEBUG dump();
  170                     DEBUG printf("Checking %d\n", i);
  171                     if (notPrinted(i))
  172                         {
  173                             /* task has not been printed yet */
  174                             DEBUG printf("%d has not been printed\n", i);
  175                             if (noPrereq(i))
  176                                 {
  177                                     /* no preReqs -- it can be printed */
  178                                     DEBUG printf("%d has no prereqs\n", i);
  179                                     if (first)
  180                                         {
  181                                             /* first time */
  182                                             first = FALSE;
  183                                         } /* first time */
  184                                     else
  185                                         {
  186                                             /* 2 through n */
  187                                             printf(" ");
  188                                         } /* 2 through n */
  189                                     DEBUG printf("\n<<");
  190                                     printf("%d", i);
  191                                     DEBUG printf(">>\n");
  192                                     rst(i);
  193                                 } /* no preReqs -- it can be printed */
  194                             else
  195                                 DEBUG printf("%d has a prereqs\n", i);
  196                         } /* task has not been printed yet */
  197                     else
  198                         DEBUG printf("%d has been printed\n", i);
  199                 } /* for each task */
  200         } /* while */
  201     printf("\n");
  202 } /* FUNCTION process */
  203 
  204 int main()
  205 {
  206     /* main */
  207     int moreToDo;
  208 
  209     init();
  210     moreToDo = getInput();
  211     while (moreToDo)
  212         {
  213             /* while */
  214             process();
  215             moreToDo = getInput();
  216         } /* while */
  217 
  218     return EXIT_SUCCESS;
  219 } /* main */
  220