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
   29      on early exit from loop(Don't just bail out of process loop if you find an
   30      invalid value)
   31  */
   32 
   33 int count;
   34 int data[MAX_ITEMS];
   35 int flags[MAX_ITEMS];
   36 
   37 void init()
   38 {
   39     /* FUNCTION init */
   40     int i;
   41 
   42     for (i=0; i<count; i++)
   43         {
   44             flags[i] = 0;
   45         }
   46 } /* FUNCTION init */
   47 
   48 void dump()
   49 {
   50     /* FUNCTION dump */
   51 } /* FUNCTION dump */
   52 
   53 int getInput()
   54 {
   55     /* FUNCTION getInput */
   56     int dataReadFlag = TRUE;
   57     int i;
   58 
   59     if (EOF == scanf(" %d ", &count))
   60         {
   61             /* then */
   62             dataReadFlag = FALSE;
   63         } /* then */
   64     else
   65         {
   66             /* else */
   67             init();
   68             for (i=0; i<count; i++)
   69                 {
   70                     scanf(" %d ",&data[i]);
   71                 }
   72         } /* else */
   73 
   74     return (dataReadFlag);
   75 } /* FUNCTION getInput */
   76 
   77 void process()
   78 {
   79     /* FUNCTION process */
   80     int i;
   81     int tmp;
   82     int res = TRUE;
   83 
   84     for (i = 0; (i < (count-1)) && (res); i ++)
   85         {
   86             /* for */
   87             tmp = abs(data[i] - data[i+1]);
   88             if ((0 != tmp) && (count > tmp) && (0 == flags[tmp]))
   89                 {
   90                     /* valid */
   91                     flags[tmp] = 1;
   92                 } /* valid */
   93             else
   94                 {
   95                     /* not valid */
   96                     res = FALSE;
   97                 } /* not valid */
   98         } /* for */
   99 
  100     if (res)
  101         {
  102             /* success */
  103             printf("Jolly\n");
  104         } /* success */
  105     else
  106         {
  107             /* failure! */
  108             printf("Not jolly\n");
  109         } /* failure! */
  110 } /* FUNCTION process */
  111 
  112 int main ()
  113 {
  114     /* main */
  115     int moreToDo;
  116 
  117     moreToDo = getInput();
  118     while (moreToDo)
  119         {
  120             /* while */
  121             process();
  122             moreToDo = getInput();
  123         } /* while */
  124 
  125     return EXIT_SUCCESS;
  126 } /* main */
  127