Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
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
пар чисел li , задающих позиции первого и последнего символа подстроки,
в которой на i-ом шаге меняются скобки.
Если существует несколько оптимальных решений, выведите любое из них.
Если решения не существует, выведите единственное число -1.
Ограничения
Длина исходной последовательности находится в диапазоне от 1 до 3000 символов.
Пример ввода 1
()
Пример вывода 1
0
Пример ввода 2
))((()
Пример вывода 2
1 1 4
Пример ввода 3
)((()((()((()(((
Пример вывода 3
2 1 16 2 7
