program Project2;

{$APPTYPE CONSOLE}

uses
  SysUtils;

type
  TMatrixInfo =
  record
    size: array [0..1] of integer;
    desc: string;
  end;

  TMatrixes =
    array [0..7] of TMatrixInfo;


var bestSolveMemoryVolume: integer;
    bestSolve: TMatrixes;
    matrixSizes: TMatrixes;


procedure GenerateSolves(solve: TMatrixes; count: integer; maxMemoryVolume: integer);
var memoryVolume:integer;
    i, j: integer;
    newSolve: TMatrixes;
begin
 
  if count=1 then
  begin
    //построение варианта решения - закончено
    //проверяем - лучшее ли оно ?
    if (maxMemoryVolume < bestSolveMemoryVolume) then
      begin
      bestSolveMemoryVolume :=  maxMemoryVolume;
      bestSolve := solve;
      end;
    exit;
  end;

  {строим варианты решения}
  for i:=0 to count-2 do
  begin
    for j:=0 to count-2 do
    if(j<i) then
      begin
        //копируем элементы
        newSolve[j].size[0] := solve[j].size[0];
        newSolve[j].size[1] := solve[j].size[1];
        newSolve[j].desc := solve[j].desc;
      end
    else
    if j=i then
      begin
        //имитируем произведение матриц i и i+1
        newSolve[j].size[0] := solve[j].size[0];
        newSolve[j].size[1] := solve[j+1].size[1];
        newSolve[j].desc := '('+solve[j].desc+'*'+solve[j+1].desc+')';
        //счтаем сколько памяти нужено под новую матрицу
        memoryVolume := newSolve[i].size[0]*newSolve[i].size[1];
        if(memoryVolume>maxMemoryVolume) then
            maxMemoryVolume :=memoryVolume;
      end
    else
      begin
        //копируем элементы
        newSolve[j].size[0] := solve[j+1].size[0];
        newSolve[j].size[1] := solve[j+1].size[1];
        newSolve[j].desc := solve[j+1].desc;
      end;
    //если текущее решение уже хуже лучшего, то не продолжаем дальше
    if maxMemoryVolume>bestSolveMemoryVolume then
      exit;
    //моделируем следующее перемножение
    GenerateSolves(newSolve, count-1, maxMemoryVolume);
  end;
 
end;


begin
matrixSizes[0].size[0] :=5;
matrixSizes[0].size[1] :=4;
matrixSizes[0].desc := 'M[5x4]';
matrixSizes[1].size[0] :=4;
matrixSizes[1].size[1] :=7;
matrixSizes[1].desc := 'M[4x7]';
matrixSizes[2].size[0] :=7;
matrixSizes[2].size[1] :=3;
matrixSizes[2].desc := 'M[7x3]';
matrixSizes[3].size[0] :=3;
matrixSizes[3].size[1] :=8;
matrixSizes[3].desc := 'M[3x8]';
matrixSizes[4].size[0] :=8;
matrixSizes[4].size[1] :=3;
matrixSizes[4].desc := 'M[8x3]';
matrixSizes[5].size[0] :=3;
matrixSizes[5].size[1] :=7;
matrixSizes[5].desc := 'M[3x7]';
matrixSizes[6].size[0] :=7;
matrixSizes[6].size[1] :=2;
matrixSizes[6].desc := 'M[7x2]';
matrixSizes[7].size[0] :=2;
matrixSizes[7].size[1] :=2;
matrixSizes[7].desc := 'M[2x2]';

bestSolveMemoryVolume := MaxInt;
//перебираем все возможные варианты, ищем лучший вариант
GenerateSolves(matrixSizes, 8, 0);

//рисуем решение
Writeln(bestSolve[0].desc);
Writeln('Max matrix: '+ intToStr(bestSolveMemoryVolume) + ' items');

Readln;

end.