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

Входные данные
Первая строка входного файла содержит заданный шаблон длиной не более 80 символов

Выходные данные
Выведите в выходной файл искомое количество способов. Исходные данные будут таковы, что это количество не превзойдет 2·109


Например:

RECOVERY.IN
????(?

RECOVERY.OUT
2





Комментарии
Рассмотрим скобочную последовательность s длины n. Пусть ci(s) равняется разности между общим количеством открывающих и закрывающих скобок среди первых i символов этой последовательности. Ясно, что s является правильным скобочным выражением тогда и только тогда, когда ci(s)
0 для всех i от 1 до n и, кроме того, сn(s) = 0

Обозначим через F(k,с) количество скобочных последовательностей s длины k, подходящих под первые k символов шаблона и таких, что сi(s)
0 для всех i от 1 до k, a ck(s)=c. Очевидно, что ответом на исходную задачу будет являться число F(N,0), где N - длина заданного шаблона

Рассмотрим задачу вычисления чисел F(k,с). Если k-ый символ шаблона - открывающая скобка, то F(k,с)=F(k-1,с-1), если закрывающая, то F(k,с)=F(k-1,c+1). Если же это знак вопроса, то на его место можно поставить как открывающую, так и закрывающую скобку, и F(k,с)=F(k-1,с-1)+F(k-1,c+1)

Получив эту формулу, задаем граничные значения F(0,c)=0, F(k,-1)=0, F(0,0)=1 и двумя вложенными циклами (внешний - по k, а внутренний - по с) последовательно вычисляем искомые числа F(k,с) для всех k от 1 до N и всех с от 0 до N. Значение F(N,0) выводим в качестве ответа

Упражнения
1. Все ли из чисел F(k,с) нам нужны для вычисления значения F(N,0)?
2. Придумайте, как обойтись в этой задаче одномерным массивом




Решение

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

program recovery; 
const 
  maxLength = 80; 
  lenMax = 100; 
  pow = 10000; 
type 
  tNumber = record 
              len : integer; 
              num : array[1..lenMax] of word; 
            end
var 
  balance, old : array[0..maxLength+10] of tNumber; 
  i, j : integer; 
  s : string
 
procedure add(var a : tNumber; const b : tNumber); 
var 
  r : word; 
  i : integer; 
begin 
  r := 0; 
  if a.len < b.len then 
    a.len := b.len; 
  for i := 1 to a.len do begin 
    inc(r, a.num[i]+b.num[i]); 
    a.num[i] := r mod pow; 
    r := r div pow; 
  end
 
  if r > 0 then begin 
    inc(a.len); 
    a.num[a.len] := 1; 
  end
end
 
procedure print(const a : tNumber); 
var 
  i : integer; 
  j : longint; 
begin 
  if a.len = 0 then 
    write(0) 
  else begin 
    write(a.num[a.len]); 
    for i := a.len-1 downto 1 do begin 
      j := a.num[i]+ord(a.num[i]=0); 
      while j*10 < pow do begin 
        write(0); 
        j := j*10; 
      end
      write(a.num[i]); 
    end
  end
 
  writeLn; 
end
 
Begin 
  assign(input, 'recovery.in'); 
  reSet(input); 
  assign(output, 'recovery.out'); 
  reWrite(output); 
 
  readLn(s); 
  fillChar(balance, sizeOf(balance), 0); 
  balance[0].len := 1; balance[0].num[1] := 1; 
  for i := 1 to length(s) do begin 
    old := balance; 
    fillChar(balance, sizeOf(balance), 0); 
 
    if (old[0].num[1] > 0) and ((s[i] = '(') or (s[i] = '?')) then 
      balance[1] := old[0]; 
 
    for j := 1 to length(s)+1 do begin 
      if (s[i] = '(') or (s[i] = '?') then 
        add(balance[j+1], old[j]); 
      if (s[i] = ')') or (s[i] = '?') then 
        add(balance[j-1], old[j]); 
    end
  end
 
  print(balance[0]); 
 
  close(input);close(output) 
End.


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