1 /* Author: Matt Eastman */
    2 #include <assert.h>
    3 #include <stdio.h>
    4 #include <stdlib.h>
    5 #include <string.h>
    6 #include <strings.h>
    7 
    8 #define FALSE 0
    9 #define TRUE 1
   10 
   11 typedef struct
   12   {
   13     char* name;
   14     int atomic_num;
   15   } Element;
   16 
   17 typedef struct
   18   {
   19     Element** elements;
   20     int num_elements;
   21     int atomic_num_sum;
   22     int obvious;
   23   } Path;
   24 
   25 Element* Element_New(char* name, int atomic_num)
   26 {
   27   Element* elem = (Element*)calloc(1, sizeof(Element));
   28   elem->name = strdup(name);
   29   elem->atomic_num = atomic_num;
   30   return elem;
   31 }
   32 
   33 void Element_Del(Element* elem)
   34 {
   35   free(elem->name);
   36   free(elem);
   37 }
   38 
   39 Path* Path_New(int num_elements)
   40 {
   41   Path* path = (Path*)calloc(1, sizeof(Path));
   42   path->elements = (Element**)calloc(num_elements, sizeof(Element*));
   43   path->num_elements = num_elements;
   44   return path;
   45 }
   46 
   47 void Path_Del(Path* path)
   48 {
   49   /* path does not own the elements themselves */
   50   free(path->elements);
   51   free(path);
   52 }
   53 
   54 /* Create a new path with elem as elements[0] and the elements of path after that */
   55 Path* Path_Combine(Path* path, Element* elem)
   56 {
   57   Path* new_path;
   58   if (path == NULL)
   59     {
   60       new_path = Path_New(1);
   61     }
   62   else
   63     {
   64       new_path = Path_New(path->num_elements + 1);
   65       memcpy(new_path->elements + 1, path->elements, sizeof(Element*) * path->num_elements);
   66       new_path->atomic_num_sum = path->atomic_num_sum;
   67       new_path->obvious = path->obvious;
   68     }
   69   new_path->elements[0] = elem;
   70   new_path->atomic_num_sum += elem->atomic_num;
   71   return new_path;
   72 }
   73 
   74 void PrintPath(Path* path)
   75 {
   76   int i;
   77   if (path == NULL)
   78     {
   79       printf("NULL\n");
   80     }
   81   else if (path->obvious)
   82     {
   83       printf("Too Obvious\n");
   84     }
   85   else
   86     {
   87       for (i = 0; i < path->num_elements; i++)
   88         {
   89           printf("[%s]", path->elements[i]->name);
   90         }
   91       printf("\n");
   92     }
   93 }
   94 
   95 int ComparePaths(Path* a, Path* b)
   96 {
   97   if (a->num_elements < b->num_elements) return -1;
   98   if (a->num_elements > b->num_elements) return 1;
   99   if (a->atomic_num_sum < b->atomic_num_sum) return -1;
  100   if (a->atomic_num_sum > b->atomic_num_sum) return 1;
  101   return 0;
  102 }
  103 
  104 Path* FindBestPath(int num_elements, Element** elements, char* word)
  105 {
  106   int i;
  107   Path* path = NULL;
  108   Path* child_path;
  109   Path* elem_path;
  110   int elem_name_len;
  111   Element* elem;
  112   int word_len = strlen(word);
  113 
  114   for (i = 0; i < num_elements; i++)
  115     {
  116       elem = elements[i];
  117       elem_name_len = strlen(elem->name);
  118       elem_path = NULL;
  119       if (strncasecmp(word, elem->name, elem_name_len) == 0)
  120         {
  121           if (elem_name_len == word_len)
  122             {
  123               elem_path = Path_Combine(NULL, elem);
  124             }
  125           else
  126             {
  127               child_path = FindBestPath(num_elements, elements, word + elem_name_len);
  128               if (child_path != NULL)
  129                 {
  130                   elem_path = Path_Combine(child_path, elem);
  131                   Path_Del(child_path);
  132                 }
  133             }
  134         }
  135       if (elem_path == NULL)
  136         {
  137           continue;
  138         }
  139       if (path == NULL)
  140         {
  141           path = elem_path;
  142           continue;
  143         }
  144 
  145       switch (ComparePaths(elem_path, path))
  146         {
  147         case -1:
  148           Path_Del(path);
  149           path = elem_path;
  150           break;
  151         case 0:
  152           Path_Del(elem_path);
  153           path->obvious = TRUE;
  154           break;
  155         default:
  156           Path_Del(elem_path);
  157         }
  158     }
  159 
  160   return path;
  161 }
  162 
  163 int main(int argc, char** argv)
  164 {
  165   int num_cases, num_elements, num_words;
  166   int i, j;
  167   char buf[1024];
  168   Element** elements;
  169   Path* path;
  170 
  171   assert(scanf(" %d", &num_cases) == 1);
  172   for (i = 0; i < num_cases; i++)
  173     {
  174       assert(scanf(" %d", &num_elements) == 1);
  175       elements = (Element**)calloc(num_elements, sizeof(Element*));
  176       for (j = 0; j < num_elements; j++)
  177         {
  178           assert(scanf(" %s", buf) == 1);
  179           elements[j] = Element_New(buf, j);
  180         }
  181       assert(scanf(" %d", &num_words) == 1);
  182       for (j = 0; j < num_words; j++)
  183         {
  184           assert(scanf(" %s", buf) == 1);
  185           path = FindBestPath(num_elements, elements, buf);
  186           assert(path != NULL);
  187           PrintPath(path);
  188           Path_Del(path);
  189         }
  190       for (j = 0; j < num_elements; j++)
  191         {
  192           Element_Del(elements[j]);
  193         }
  194       free(elements);
  195     }
  196   return 0;
  197 }
  198