Задача

Жадный калькулятор
COVETOUS

Условие Комментарии Решение Тестовые файлы Оглавление

Задача
Задано алгебраическое выражение, составленное из неотрицательных вещественных чисел и знаков операций "+", "-" и "*". Требуется так расставить в этом выражении скобки, чтобы его значение стало максимально возможным

Входные данные
Исходное выражение длиной не более 250 символов записано в первой строке входного файла. Выражение содержит не более 50 чисел, каждое из которых лежит в диапазоне от 0 до 10⁶. Пробелы внутри чисел не допускаются

Выходные данные
Выведите в первую строку выходного файла максимально возможное после расстановки скобок значение выражения, а во вторую строку - само выражение. Если вариантов несколько, нужно вывести любой из них

Например:

COVETOUS.IN
1+2-3.0*4

COVETOUS.OUT
0
((1+2)-3)*4

Идеи
Динамическое программирование, длинная арифметика

Комментарии
Пусть задано некоторое алгебраическое выражение, содержащее N чисел. Рассмотрим кусок этого выражения, расположенный между i-ым и j-ым его числами включительно (1ij N). Пусть Max(i,j) обозначает максимально возможное после расстановки скобок значение этого куска, a Min(i,j) -минимально возможное. Эти числа следует вычислять парами в порядке увеличения длин кусков j-i+1. Ясно, что для всех i от 1 до N значения Max(i,i) и Min(i,i) совпадают и равны i-му числу выражения. При i<j число Max(i,j) вычисляем следующим образом. Перебираем все значения k, такие что ik<j, и каждый раз предполагаем, что при вычислении значения рассматриваемого куска самой последней выполняется операция, записанная между числами с номерами k и k+1. Если это, к примеру, операция вычитания, то чтобы максимизировать значение части выражения от i-го числа до j-го, мы должны взять максимальное значение куска от i-го числа до k-го (которое уже вычислено) и вычесть из него минимальное значение куска от (k+1)-гo числа до j-го (которое также уже вычислено). Из значений, полученных при анализе различных k, выбираем максимальное. Операции "+" и "*" и вычисление Min(i,j) рассматриваются аналогично

Решение

{$A+,B-,D+,E+,F-,G-,I+,L+,N+,O-,P-,Q-,R-,S+,T-,V+,X+,Y+}
{$M 16384,0,655360}

program covetous;
type extended = double;
const nmax=50;
      max:extended=1.7e300;
type from=record
     k,s1,s2:byte;
     end;
var ma,mi:array[1..nmax,1..nmax] of extended;   { [ з «®, ¤«Ё ] }
    z:array[1..nmax] of byte; { 0 + 1 * }
    x:array[1..nmax,1..nmax,1..2] of from;
    n:integer;
    s:string;
    us:byte;

procedure del_spaces;
    begin
    while (s[us]=' ') and (us<=length(s)) do inc(us);
    end;

function read_cislo:extended;
    var pp:string;
        i:integer;
        j:extended;
    begin
    del_spaces;
    pp:='';
    while s[us] in ['0'..'9','.'] do begin
      pp:=pp+s[us];
      inc(us);
      end;
    val(pp,j,i);
    read_cislo:=j;
    end;

function read_znak:byte;
    begin
    del_spaces;
    if us>length(s) then read_znak:=10
    else begin
         if s[us]='+' then read_znak:=0 else
          if s[us]='*' then read_znak:=1
            else read_znak:=2;
         inc(us);
         end;
    end;

procedure init;
    begin
    assign(input,'covetous.in');
    reset(input);
    assign(output,'covetous.out');
    rewrite(output);
    readln(s);
    us:=1;
    n:=0;
    repeat
      inc(n);
      ma[n,1]:=read_cislo;
      mi[n,1]:=ma[n,1];
      z[n]:=read_znak;
    until z[n]=10;
    close(input);
    end;

procedure scet;
    var i,j,k:integer;
        e:extended;
    begin
    for i:=2 to n do
      for j:=1 to n+1-i do begin
        ma[j,i]:=-max;
        mi[j,i]:=max;
        for k:=1 to i-1 do begin
          case z[j+k-1] of
          0:e:=ma[j,k]+ma[j+k,i-k];
          1:e:=ma[j,k]*ma[j+k,i-k];
          2:e:=ma[j,k]-ma[j+k,i-k];
          end;
          if e>ma[j,i] then begin ma[j,i]:=e;x[j,i,1].k:=k;
                                  x[j,i,1].s1:=1;x[j,i,1].s2:=1;end;
          if e then begin mi[j,i]:=e;x[j,i,2].k:=k;
                                  x[j,i,2].s1:=1;x[j,i,2].s2:=1;end;
          case z[j+k-1] of
          0:e:=mi[j,k]+ma[j+k,i-k];
          1:e:=mi[j,k]*ma[j+k,i-k];
          2:e:=mi[j,k]-ma[j+k,i-k];
          end;
          if e>ma[j,i] then begin ma[j,i]:=e;x[j,i,1].k:=k;
                                  x[j,i,1].s1:=2;x[j,i,1].s2:=1;end;
          if e then begin mi[j,i]:=e;x[j,i,2].k:=k;
                                  x[j,i,2].s1:=2;x[j,i,2].s2:=1;end;
          case z[j+k-1] of
          0:e:=ma[j,k]+mi[j+k,i-k];
          1:e:=ma[j,k]*mi[j+k,i-k];
          2:e:=ma[j,k]-mi[j+k,i-k];
          end;
          if e>ma[j,i] then begin ma[j,i]:=e;x[j,i,1].k:=k;
                                  x[j,i,1].s1:=1;x[j,i,1].s2:=2;end;
          if e then begin mi[j,i]:=e;x[j,i,2].k:=k;
                                  x[j,i,2].s1:=1;x[j,i,2].s2:=2;end;
          case z[j+k-1] of
          0:e:=mi[j,k]+mi[j+k,i-k];
          1:e:=mi[j,k]*mi[j+k,i-k];
          2:e:=mi[j,k]-mi[j+k,i-k];
          end;
          if e>ma[j,i] then begin ma[j,i]:=e;x[j,i,1].k:=k;
                                  x[j,i,1].s1:=2;x[j,i,1].s2:=2;end;
          if e then begin mi[j,i]:=e;x[j,i,2].k:=k;
                                  x[j,i,2].s1:=2;x[j,i,2].s2:=2;end;

          end;
        end;
    writeln(ma[1,n]);
    end;

procedure rec(q,w,r:integer);
    begin
    if w=1 then begin
      if r=1 then write(ma[q,w]) else write(mi[q,w]);
      exit;
      end;
    write('(');
    rec(q,x[q,w,r].k,x[q,w,r].s1);
    case z[q+x[q,w,r].k-1] of
      0:write('+');
      1:write('*');
      2:write('-');
      end;
    rec(q+x[q,w,r].k,w-x[q,w,r].k,x[q,w,r].s2);
    write(')');
    end;

procedure outter;
begin
    rec(1,n,1);
    writeln;
end;

Begin
init;
scet;
outter;
close(output);
End.

Замечание (CHAS)
Представленное авторами решение в результирующий файл выдает несколько иной вариант ответа, нежели приведенный в условии. Например, для приведенных в условии входных данных результатом является:

COVETOUS.OUT
0.00000000000000E+0000
((1.00000000000000E+0000+(2.00000000000000E+0000-3.00000000000000E+0000))*4.00000000000000E+0000)