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 <stdlib.h>
    7 #include <math.h>
    8 #include <stdint.h>
    9 #include <ctype.h>
   10 
   11 #define TRUE  (1 == 1)
   12 #define FALSE (1 != 1)
   13 
   14 #define DEBUG if (TRUE)
   15 
   16 /* fprintf(stderr, "functionName: message", varslist); */
   17 
   18 /*
   19  *  Author: Isaac Traxler
   20  *    Date: 2025-04-30
   21  * Purpose: fun
   22  * Problem: 12081 - Reduced ID Numbers
   23  */
   24 
   25 /*
   26  * This template reads data a specified number of times.
   27  */
   28 
   29 #define MAX_GROUPS 1500
   30 
   31 int numberOfTimes;
   32 int g[MAX_GROUPS];
   33 int ary[MAX_GROUPS];
   34 int gCnt;
   35 int ans;
   36 
   37 
   38 void init()
   39 {
   40     /* FUNCTION init */
   41     scanf("%d ", &numberOfTimes);
   42 } /* FUNCTION init */
   43 
   44 void clearAry()
   45 {
   46     /* FUNCTION clearAry */
   47     int i;
   48 
   49     for (i=0; i<MAX_GROUPS; i++)
   50         {
   51             ary[i] = 0;
   52         }
   53 } /* FUNCTION clearAry */
   54 
   55 int sumAry()
   56 {
   57     /* FUNCTION sumAry */
   58     int i;
   59     int sm = 0;
   60 
   61     for (i=0; i<ans; i++)
   62         {
   63             sm = sm + ary[i];
   64         }
   65     return sm;
   66 } /* FUNCTION sumAry */
   67 
   68 void getInput()
   69 {
   70     /* FUNCTION getInput */
   71     int i;
   72 
   73     scanf(" %d ", &gCnt);
   74     for (i=0; i<gCnt; i++)
   75         {
   76             /* for each SIN of the group */
   77             scanf(" %d ", &g[i]);
   78         } /* for each SIN of the group */
   79 } /* FUNCTION getInput */
   80 
   81 void process()
   82 {
   83     /* FUNCTION process */
   84     int tot;
   85     int i;
   86     int tmp;
   87 
   88 
   89     if (1 == gCnt)
   90         {
   91             printf("1\n");
   92         }
   93     else
   94         {
   95             /* we have to figure this out */
   96             tot = 0;
   97             ans = 1;
   98             while (tot < gCnt)
   99                 {
  100                     /* try another bit */
  101                     clearAry();
  102                     ans++;
  103                     DEBUG printf("(tot: %d) (ans: %d)\n", tot, ans);
  104                     for (i=0; i<gCnt; i++)
  105                         {
  106                             /* do each SIN */
  107                             tmp = g[i] % ans;
  108                             DEBUG printf("(i: %4d) (tmp: %4d) (ary[%4d]: %4d) (g[%4d]: %4d)\n", tmp, tmp, ary[tmp], i, g[i]);
  109                             if (1 == ary[tmp])
  110                                 {
  111                                     i = gCnt + 1;    /* bail out if collision */
  112                                 }
  113                             ary[tmp] = 1;
  114                         } /* do each SIN */
  115                     tot = sumAry();
  116                     DEBUG printf("(case: %d)  (tot: %d) (ans: %d)\n", numberOfTimes, tot, ans);
  117                 } /* try another bit */
  118             printf("%d\n", ans);
  119         } /* we have to figure this out */
  120 } /* FUNCTION process */
  121 
  122 int main()
  123 {
  124     /* main */
  125     int i;
  126 
  127     init();
  128     for (i=0; i<numberOfTimes; i++)
  129         {
  130             /* while */
  131             getInput();
  132             process();
  133         } /* while */
  134 
  135     return EXIT_SUCCESS;
  136 } /* main */
  137 
  138