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

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

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

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


Например:

RECOVERY.IN
????(?

RECOVERY.OUT
2




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

Обозначим через F(k,с) количество скобочных последовательностей s длины k, подходящих под первые k символов шаблона и таких, что с_i(s)0 для всех i от 1 до k, a c_k(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.

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