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

struct Matrix
{
   int rows;
   int cols;
};

struct Matrices
{
   struct Matrix * items;
   int number;
};


struct Solution
{
   int cost;
   int middle1;
   int middle2;
};


struct Solution ** malloc2d(int rows, int columns)
{ 
   int row;
   struct Solution ** result = malloc(rows * sizeof(struct Solution *));
   for (row = 0; row < rows; row++)
      result[row] = malloc(columns * sizeof(struct Solution));
   
   return result;
}


void free2d(struct Solution ** array, int rows, int columns)
{ 
   int row;
   for (row = 0; row < rows; row++)
      free(array[row]);
   
   free(array);
}


struct Result
{
   char * ordering;
   int cost;
};

struct Matrices read_matrices(char * filename)
{
   struct Matrices result;
   result.number = 0;
   result.items = 0;

   FILE * handle = fopen(filename, "rb");
   if (handle == 0)
   {
      printf("cannot open %s\n", filename);
      return result;
   }

   fscanf(handle, "%d", &(result.number));
   result.items = malloc(sizeof(struct Matrix) * result.number);
   printf("number = %d\n", result.number);

   int counter;
   for (counter = 0; counter < result.number; counter++)
   {
      int rows, cols; 
      fscanf(handle, "%d %d", & rows, & cols);
      result.items[counter].rows = rows;
      result.items[counter].cols = cols;
      printf("%3d: rows = %4d,   cols = %4d\n", counter, rows, cols);
      if ((counter >= 1) && (rows != result.items[counter-1].cols))
      {
         printf("error, rows/cols mismatch\n");
         exit(1);
      }
   }

   return result;
}


char * get_ordering(struct Matrices input, struct Solution ** solutions, int start, int finish)
{
   struct Matrix * matrices = input.items;
   int number = input.number;
   char * result;
 
   if (start == finish)
  {
      result = malloc(sizeof(char) * 20);
      sprintf(result, "%d", start);
      return result;
   }

   struct Solution solution = solutions[start][finish];
   char * first = get_ordering(input, solutions, start, solution.middle1);
   char * second = get_ordering(input, solutions, solution.middle2, finish);
   result = malloc(sizeof(char) * (finish - start +1) * 20);
   sprintf(result, "(%s * %s)", first, second);
   free(first);
   free(second);

   return result;
}
   

struct Result optimal_ordering(struct Matrices input)
{
   struct Matrix * matrices = input.items;
   int number = input.number;
   struct Solution ** solutions = malloc2d(number, number);
   int first, second, third;
   for (first = 0; first < number; first++)
   {
      for (second = first; second >= 0; second--)
     {
         struct Solution solution;
         if (second == first)
         {
            solution.cost = 0;
            solution.middle1 = second;
            solution.middle2 = first;
            solutions[second][first] = solution;
            continue;
         }
         if (second == first-1)
         {
            solution.cost = matrices[second].rows * matrices[first].rows * matrices[first].cols;
            solution.middle1 = second;
            solution.middle2 = first;
            solutions[second][first] = solution;
            continue;
         }
         
         solution.cost = -1;
         for (third = second; third <= first -1; third++)
         {
            int cost1 = solutions[second][third].cost;
            int cost2 = solutions[third+1][first].cost;
            int rows1 = matrices[second].rows;
            int rows2 = matrices[third+1].rows;
            int cols = matrices[first].cols;
            int cost3 =  rows1 * rows2 * cols;
            int cost = cost1+ cost2+ cost3;
            if ((cost < solution.cost) || (solution.cost == -1))  
            {
               solution.cost = cost;
               solution.middle1 = third;
               solution.middle2 = third +1;               
            }
         }
         
         solutions[second][first] = solution;
     }
   }

   struct Result result;
   result.ordering = get_ordering(input, solutions, 0, number-1);
   result.cost = solutions[0][number-1].cost;
   free2d(solutions, number, number);
   return result;
}
      
      
int main()
{
   struct Matrices matrices = read_matrices("omm1.txt");
   struct Result result = optimal_ordering(matrices);
   printf(" optimal ordering = %s\n", result.ordering);
   printf(" optimal cost = %d\n", result.cost);

   free(result.ordering);
   free(matrices.items);
   return 0; 
}