|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 03-1. Восстановление скобок.
(Разбор)
Пусть дана скобочная последовательность. Заведем счетчик, равный изначально нулю. Теперь будем двигаться по нашей последовательности и увеличивать счетчик, если встретили открывающуюся скобку и уменьшать в противном случае. Если счетчик всегда был неотрицательный и в конце стал равен 0, то данная скобочная последовательность является правильной. Значение этого счетчика после обработки данного элемента последовательности будем называть "балансом" части последовательности с первого по данный элемент.
Будем решать задачу нахождения количества скобочных последовательностей, удовлетворяющих первым k символам шаблона, у которых баланс всегда неотрицателен и в конце равен m (обозначим количество таких последовательностей ak,m). Есть два варианта: либо на k-м месте стоит открывающаяся скобка, тогда последовательность из k-1 скобки (без последней) должна иметь баланс m-1 - таких последовательностей ak-1,m-1, либо закрывающаяся - тогда, наоборот, баланс последовательности без последней скобки равен m+1 - таких последовательностей ak-1,m+1. В зависимости от шаблона и баланса возможны один, два (если в шаблоне стоит на этом месте ?) или ноль из этих вариантов. ak,m равно их сумме. Ответ на поставленную задачу будет в an,0.
Нужно отметить одну тонкость. В условии сказано, что окончательный ответ входит в стандартный тип longint, но не сказано, что все промежуточные вычисления укладываются в longint. Однако, если в ходе вычислений мы получили какое-то большое число, то оно не может влиять на окончательный ответ (так как при вычислении ответа используется только сумма). Значит, это число можно либо вообще не вычислять, либо вычислить с ошибками. На окончательный результат это не повлияет.