ACSU Programming Competition

21 September 1996

Results and Solutions

Problems

The problems were available as a Microsoft Word document. However, I was informed that the document was infected with the Word macro virus. I will repost the problems once the virus has been removed. If you'd like to see some sample problems, go to the 1996 ACM International contest problems. Keep in mind that our problems will be similar, but much easier.

Results

Four contestants correctly answered three problems. They were:
  1. Xun Huang, 418 minutes
  2. Hector Yee, 470 minutes
  3. Ed Wayt, 588 minutes
  4. Martin Handwerker, 831 minutes
Four contestants correctly answered two problems. They were:
  1. Nisheeth Renjan, 221 minutes
  2. Sandeep Tamhankar, 269 mintues
  3. Chris Heisterkamp, 280 minutes
  4. Walter Bell, 374 minutes

Solutions

There were 6 problems. Only problems 1 through 4 had correct submissions. As a result, I am only posting the solutions to these problems.

Problem 1 -- Base -2

int base_m2(int i)
{
int n, acc, sign;

for (n = 4096, acc = 0, sign = 1; n >= 1; n /= 2, sign = - sign)
   acc += sign * ((i / n) % 2) * n;
return acc;
}

void print_base_2(int i)
{
int n;

for (n = 4096; n >= 1; n /= 2)
   if (((i / n) % 2) != 0) break;
for (; n >= 1; n /= 2)
   printf("%d", (i / n) % 2);
}

void main(void)
{
int i, j;

do {
   scanf("%d", &i);
   if (i == 0) return;
   printf("%5d base 10 = ", i);
   for (j = 0; j < 4096; j++)
      if (base_m2(j) == i)
         {
         print_base_2(j);
         break;
         }
   printf(" base -2\n");
   } while (1);
}

Problem 2 -- Beekeeper

int day = 0;
double honey = 20.0;
int num = 0;
double net;
typedef struct {
   int day;
   double grams;
   } queen_type;
queen_type queen;
int drone[50000];

void main(void)
{
int i, j;
scanf("%lf", &net);
queen.day = 0;
queen.grams = 0.5;
do {
   day ++;
   queen.day ++;
   if (queen.day < 7)
      {
      honey -= queen.grams;
      queen.grams *= 1.5;
      }
   if (queen.day >= 3)
      for (i = 1; i <= 5; i++)
         {
         num ++;
         drone[num] = 0;
         }
   if (queen.day == 7)
      {
      queen.day = 1;
      queen.grams = 0.5;
      honey -= queen.grams;
      queen.grams *= 1.5;
      }
   j = 1;
   while (j <= num)
      {
      drone[j] ++;
      if (drone[j] > 2)
         honey += net;
      if (drone[j] == 20)
         {
         drone[j] = drone[num];
         num --;
         }
         else j ++;
      }
   } while (honey < 100000.0);
printf("It will take %d days to produce 100 kilograms of honey.\n", day);
}

Problem 3 -- The Tickler

void main(void)
{
int m[50], d[50], y[50], mm, dd, yy, i, j;
char e[50][50], ee[50];
int n = 0;

for (n = 0; (read_line(m+n, d+n, y+n, e+n) != 0); n++);

for (i = 0; (read_line(&mm, &dd, &yy, ee) != 0); i++)
   {
   printf("%d/%d/%d\n", mm, dd, yy);
   for (j = 0; j < n; j++)
      if ( ((mm == m[j]) || (m[j] == -1))
         &&((dd == d[j]) || (d[j] == -1))
         &&((yy == y[j]) || (y[j] == -1)) )
         printf("%s\n", e[j]);
   printf("\n");
   }
}

int read_line(int *m, int *d, int *y, char *e)
{
int i = 0, j, ret;
char line[80];

if (gets(line) == NULL) return 0;
if (line[0] == 0) return 0;

ret = sscanf(line, "%d", m);
if (ret == 0) *m = -1;
for (j = 0; line[j] != '/'; j++);
ret = sscanf(&(line[j+1]), "%d", d);
if (ret == 0) *d = -1;
j++;
for (; line[j] != '/'; j++);
ret = sscanf(&(line[j+1]), "%d", y);
if (ret == 0) *y = -1;

for (; line[j] > ' '; j++)
   if (line[j] == 0) return 1;
for (; line[j] <= ' '; j++)
   if (line[j] == 0) return 1;
strcpy(e, &(line[j]));

return 1;
}

Problem 4 -- Very Long Multiplication

#define MAX_DIG 101

void in_num(int *f)
{
int in[MAX_DIG];
int j, k;

for (j = 0; (in[j] = getchar()) >= '0'; j++) in[j] -= '0';
for (k = j-1; k >= 0; k--) f[j-1-k] = in[k];
f[j] = 0;
}

void print_num(int *f)
{
int j;

for (j = MAX_DIG-1; (f[j] == 0) && (j > 0); j--);
for (; j >= 0; j--)
   {
   printf("%c", f[j]+'0');
   if ((j % 3 == 0) && (j != 0)) printf(",");
   }
printf("\n");
}

void main(void)
{
int n, i, j1, j2, k, f1[MAX_DIG], f2[MAX_DIG], f3[MAX_DIG];

scanf("%d", &n);
scanf("\n");
for (i = 0; i < n; i++)
   {
   for (k = 0; k < MAX_DIG; k++) f1[k] = f2[k] = f3[k] = 0;
   in_num(f1);
   in_num(f2);
   for (j2 = 0; j2 < MAX_DIG; j2 ++)
      for (j1 = 0; j1 < MAX_DIG - j2; j1++)
         {
         f3[j1+j2] += f1[j1] * f2[j2];
         f3[j1+j2+1] += f3[j1+j2] / 10;
         f3[j1+j2] %= 10;
         }
   print_num(f3);
   }
}
Last updated 7 September 1997.