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

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

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


Например:

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)
 


© Особенности национальных задач по информатике