Saving the Universe

My solution for the Saving the Universe task of Google Code Jam 2008 qualification round:


#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct {
  char *name;
  int num;
} ENGINE;

int cmpEngines(const void *v1, const void *v2) {
  ENGINE *e1 = (ENGINE*)v1, *e2 = (ENGINE*)v2;
  return strcmp(e1->name, e2->name);
}

int askEngineNum(char *name, ENGINE *base, int numb) {
  ENGINE key, *ind;
  key.name = name;
  ind = bsearch(&key, (void*)base, (size_t)numb, sizeof(*base), &cmpEngines);
  return ind->num;  
}

main() {
  int MASK[100];
  char str[4096];
  int N, S, Q;
  int iN, i;
  int curEngine;
  int result;

  int usedEngines;
  ENGINE dict[100];

  fgets(str, sizeof(str), stdin);
  sscanf(str, "%d", &N);
  fprintf(stderr, "N:%d\n", N);

  for (iN = 0; iN < N; iN++) {

    result = 0;
    usedEngines = 0;

    fgets(str, sizeof(str), stdin);
    sscanf(str, "%d", &S);
     
    bzero(MASK, sizeof(MASK));

    for(i = 0; i < S; i++) {
      fgets(str, sizeof(str), stdin);
      dict[i].name = strdup(str);
      dict[i].num = i;
    }
    qsort(dict, (size_t)S, sizeof(*dict), &cmpEngines);
 
    fgets(str, sizeof(str), stdin);
    sscanf(str, "%d", ∓Q);
  
    for(i = 0; i < Q; i++) {
      fgets(str, sizeof(str), stdin);
      curEngine = askEngineNum(str, dict, S);
       if (MASK[curEngine] == 0) {
 	if (++usedEngines == S) {
	  result++;
	  bzero(MASK, sizeof(MASK));
	  usedEngines = 1;
	}
 	MASK[curEngine] = 1;
      }
    }
    
    for(i = 0; i < S; i++) free(dict[i].name);

    fprintf(stdout, "Case #%d: %d\n", iN + 1, result);

  }
  return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *