НачалоПодразделы
Другие разделы
Дата и время
22/11/2024 00:03:49
1018. Замена скобок: минимизация шагов
Замена скобок: минимизация шагов
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 03/07/2008 | Лето 2008 дорешивание (10D) |
| 23/07/2008 | Лето 2008 - 10 (D) |
Ограничения: время – 1s/2s, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Рассмотрим последовательность из открывающихся и закрывающихся круглых скобок.
Назовём такую последовательность скобочной. Скобочная последовательность
называется правильной, если она может быть построена
по следующим законам:
- пустая строка является правильной скобочной последовательностью;
- если `S` –- правильная скобочная последовательность, то (`S`) – тоже правильная скобочная последовательность;
- если `A` и `B` –- правильные скобочные последовательности, то `"AB"` – тоже правильная скобочная последовательность.
Примеры правильных скобочных последовательностей —
"()", "((()))", "()()()", "((()())())(())".
Неформально говоря, правильная скобочная последовательность — это
последовательность скобок, которая может быть получена из некоторого
арифметического выражения удалением из него всего, кроме скобок.
Рассмотрим следующий алгоритм: на каждом шаге выбирается подстрока скобочной
последовательности и скобки в ней меняются на противоположные, то есть все символы '('
в этой подстроке заменяются на ')', а все символы ')' – на '('.
Требуется написать программу, которая по скобочной последовательности рассчитает
минимальное количество шагов `N`, необходимое для превращения её в правильную.
Ввод
Во входном файле содержится скобочная последовательность.
Вывод
В выходном файле должно содержаться число `N`, за которым следуют `N`
пар чисел `l_i\ r_i`, задающих позиции первого и последнего символа подстроки,
в которой на `i`-ом шаге меняются скобки.
Если существует несколько оптимальных решений, выведите любое из них.
Если решения не существует, выведите единственное число `-1`.
Ограничения
Длина исходной последовательности находится в диапазоне от 1 до 3000 символов.
Пример ввода 1
()
Пример вывода 1
0
Пример ввода 2
))((()
Пример вывода 2
1 1 4
Пример ввода 3
)((()((()((()(((
Пример вывода 3
2 1 16 2 7
