program optimaltree (input, output);
  const
    maxkeys = 30;
  type
    index = 0..maxkeys;
  var
    n: index;                                     {number of keys}
    key: array[index] of integer;    {keys}
    p: array[index] of real;             {probability of hitting key}
    q: array[index] of real;             {probability of missing between keys}
    c: array[index, index] of real;   {cost of subtree}
    r: array[index, index] of index; {root of subtree}
    w: array[index, index] of real;  {accumulated p and q}
    i, j: index;

  procedure opttree;
    var
      x, min: real;
      i, j, k, h, m: index;
  begin {argument:w, result: p,r}
    for i := 0 to n do
      c[i, i] := 0;  {width of tree h=0}
    for i := 0 to n - 1 do {width of tree h=1}
      begin
        j := i + 1;
        c[i, j] := w[i, j];
        r[i, j] := j
      end;
    for h := 2 to n do                   {h=width of considered tree}
      for i := 0 to n - h do            {i=left index of considered tree}
        begin                                 {j=right index of considered tree}
          j := i + h;
          writeln('building c(', i : 1, ',', j : 1, ') using roots ', r[i, j - 1] : 1, ' thru ', r[i + 1, j] : 
1);
          m := r[i, j - 1];
          min := c[i, m - 1] + c[m, j];
          for k := m + 1 to r[i + 1, j] do
            begin
              x := c[i, k - 1] + c[k, j];
              if x < min then
                begin
                  m := k;
                  min := x
                end
            end;
          c[i, j] := min + w[i, j];
          r[i, j] := m
        end
  end; {opttree}

  procedure prefix (i, j: index);
{prints the optimal binary search tree}
  begin
    if i < j then
      begin
        write(key[r[i, j]] : 1);
        if (i < (r[i, j] - 1)) and (r[i, j] < j) then
          begin
            write('(');
            prefix(i, r[i, j] - 1);
            write(',');
            prefix(r[i, j], j);
            write(')')
          end
        else if i < (r[i, j] - 1) then
          begin
            write('(');
            prefix(i, r[i, j] - 1);
            write(',');
            write(')')
          end
        else if r[i, j] < j then
          begin
            write('(');
            write(',');
            prefix(r[i, j], j);
            write(')')
          end
      end
  end;

begin {main}
{read in problem instance here}
  n := 5;
  q[0] := 0.2;
  key[1] := 10;
  p[1] := 0.09;
  q[1] := 0.2;
  key[2] := 20;
  p[2] := 0.1;
  q[2] := 0.03;
  key[3] := 30;
  p[3] := 0.2;
  q[3] := 0.04;
  key[4] := 40;
  p[4] := 0.02;
  q[4] := 0.01;
  key[5] := 50;
  p[5] := 0.05;
  q[5] := 0.06;

  for i := 0 to n do
    begin
      w[i, i] := q[i];
      writeln('w[', i : 1, ',', i : 1, ']=', w[i, i] : 10 : 4);
      for j := i + 1 to n do
        begin
          w[i, j] := w[i, j - 1] + p[j] + q[j];
          writeln('w[', i : 1, ',', j : 1, ']=', w[i, j] : 10 : 4)
        end
    end;
  opttree;
  writeln('Average probe length is ', c[0, n] / w[0, n] : 10 : 4);
  writeln('trees in parenthesized prefix');
  for i := 0 to n do
    for j := 0 to n - i do
      begin
        write('C(', j : 1, ' ', j + i : 1, ') cost ', c[j, j + i] : 10 : 4, ' ');
        prefix(j, j + i);
        writeln
      end
end.