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 512
   30 
   31 int numberOfTimes;
   32 int g[MAX_GROUPS];
   33 int ary[MAX_GROUPS];
   34 int gCnt;
   35 int mask;
   36 char buff[80];
   37 
   38 
   39 void init()
   40 {
   41     /* FUNCTION init */
   42     scanf("%d ", &numberOfTimes);
   43 } /* FUNCTION init */
   44 
   45 void print2buff(unsigned int n)
   46 {
   47     int i;
   48     int tmp;
   49     int d;
   50     char charSet[2] = {'0', '1'};
   51 
   52     tmp = n;
   53     i = 0;
   54     while (tmp > 0)
   55         {
   56             /* while */
   57             d = 1 & tmp;
   58             buff[i] = charSet[d];
   59             i++;
   60             tmp = tmp >> 1;
   61         }
   62     buff[i] = 0;
   63 }
   64 
   65 
   66 
   67 void clearAry()
   68 {
   69     /* FUNCTION clearAry */
   70     int i;
   71 
   72     for (i=0; i<gCnt; i++)
   73         {
   74             ary[i] = 0;
   75         }
   76 } /* FUNCTION clearAry */
   77 
   78 int sumAry()
   79 {
   80     /* FUNCTION sumAry */
   81     int i;
   82     int sm = 0;
   83 
   84     for (i=0; i<=mask; i++)
   85         {
   86             sm = sm + ary[i];
   87         }
   88     return sm;
   89 } /* FUNCTION sumAry */
   90 
   91 void getInput()
   92 {
   93     /* FUNCTION getInput */
   94     int i;
   95 
   96     scanf(" %d ", &gCnt);
   97     for (i=0; i<gCnt; i++)
   98         {
   99             /* for each SIN of the group */
  100             scanf(" %d ", &g[i]);
  101         } /* for each SIN of the group */
  102 } /* FUNCTION getInput */
  103 
  104 void process()
  105 {
  106     /* FUNCTION process */
  107     int tot;
  108     int i;
  109     int ans;
  110     int tmp;
  111 
  112 
  113     if (1 == gCnt)
  114         {
  115             printf("1\n");
  116         }
  117     else
  118         {
  119             /* we have to figure this out */
  120             tot = 0;
  121             ans = 0;
  122             mask = 0;
  123             while (tot < gCnt)
  124                 {
  125                     /* try another bit */
  126                     mask = mask * 2 + 1;
  127                     DEBUG printf("(tot: %d) (mask: %d) (ans: %d)\n", tot, mask, ans);
  128                     clearAry();
  129                     for (i=0; i<gCnt; i++)
  130                         {
  131                             /* do each SIN */
  132                             tmp = g[i] & mask;
  133                             ary[g[i]&mask] = 1;
  134                             DEBUG print2buff(g[i]);
  135                             DEBUG printf("(tmp: %d) (ary[%d]: %d) (g[%d]: %d:%s)\n", tmp, tmp, ary[tmp], i, g[i], buff);
  136                         } /* do each SIN */
  137                     tot = sumAry();
  138                 } /* try another bit */
  139             printf("%d\n", mask + 1);
  140         } /* we have to figure this out */
  141 } /* FUNCTION process */
  142 
  143 int main()
  144 {
  145     /* main */
  146     int i;
  147 
  148     init();
  149     for (i=0; i<numberOfTimes; i++)
  150         {
  151             /* while */
  152             getInput();
  153             process();
  154         } /* while */
  155 
  156     return EXIT_SUCCESS;
  157 } /* main */
  158 
  159