Computer Programming Contest Preparation

    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 
   10 #define TRUE  (1 == 1)
   11 #define FALSE (1 != 1)
   12 
   13 #define DEBUG if (FALSE)
   14 #define MAX_ITEMS 3005
   15 
   16 /*
   17  *  Author: Josh Abadie/Isaac Traxler
   18  *    Date: 2008 03 03
   19  * Purpose:
   20  * Problem: 10038 - Jolly Jumpers
   21  */
   22 
   23 /*
   24 
   25   possible optimizations:
   26   1) Make flags an array of bytes (reduce storage, may increase runtime)
   27   2) Eliminate data array and use current previous (you only need 2 at a time)
   28   3) Move process up into input -- but have to remember to finish reading input on early exit from loop(Don't just bail out of process loop if you find an invalid value)
   29  */
   30 
   31 int count;
   32 int flags[MAX_ITEMS];
   33 
   34 void init()
   35 {
   36     /* FUNCTION init */
   37     int i;
   38 
   39     for (i=0; i<count; i++)
   40         {
   41             flags[i] = 0;
   42         }
   43 } /* FUNCTION init */
   44 
   45 void dump()
   46 {
   47     /* FUNCTION dump */
   48 } /* FUNCTION dump */
   49 
   50 int getInput()
   51 {
   52     /* FUNCTION getInput */
   53     int dataReadFlag = TRUE;
   54     int i;
   55 
   56     if (EOF == scanf(" %d ", &count))
   57         {
   58             /* then */
   59             dataReadFlag = FALSE;
   60         } /* then */
   61     else
   62         {
   63             /* else */
   64             init();
   65         } /* else */
   66 
   67     return (dataReadFlag);
   68 } /* FUNCTION getInput */
   69 
   70 void process()
   71 {
   72     /* FUNCTION process */
   73     int i;
   74     int tmp;
   75     int res = TRUE;
   76     int curr, prev;
   77 
   78     scanf(" %d ",&prev);
   79     for (i = 1; (i < (count)); i ++)
   80         {
   81             /* for */
   82             scanf(" %d ",&curr);
   83             if (res)
   84                 {
   85                     /* Failure.  Read in rest of input */
   86                     tmp = abs(curr - prev);
   87                     if ((0 != tmp) && (count > tmp) && (0 == flags[tmp]))
   88                         {
   89                             /* valid */
   90                             flags[tmp] = 1;
   91                         } /* valid */
   92                     else
   93                         {
   94                             /* not valid */
   95                             res = FALSE;
   96                         } /* not valid */
   97                     prev = curr;
   98                 } /* Failure.  Read in rest of input */
   99         } /* for */
  100 
  101     if (res)
  102         {
  103             /* success */
  104             printf("Jolly\n");
  105         } /* success */
  106     else
  107         {
  108             /* failure! */
  109             printf("Not jolly\n");
  110         } /* failure! */
  111 } /* FUNCTION process */
  112 
  113 int main ()
  114 {
  115     /* main */
  116     int moreToDo;
  117 
  118     moreToDo = getInput();
  119     while (moreToDo)
  120         {
  121             /* while */
  122             process();
  123             moreToDo = getInput();
  124         } /* while */
  125 
  126     return EXIT_SUCCESS;
  127 } /* main */
  128