Начало
ЗадачиПодразделы
Другие разделы
| STL |
| Антагонистические игры |
| Геометрия |
| Графы |
| Дихотомия |
| Длинная арифметика |
| Комбинаторика |
| Неклассифицированные |
| Основы |
| Перебор |
| Поиск в глубину |
| Поиск в ширину |
| Последовательности |
| Сортировка |
| Теория чисел |
Дата и время
17/11/2024 09:19:16
Динамическое программирование
And Then There Was One Broken Sword: потерянный файл Decoding Morse Sequences SMS Бросание кубика Витрина Возрастающая подпоследовательность Гангстеры Головоломка умножения Зоопарк Копилка Кубический метр Маршрут Палиндром Разложение на простые слагаемые Скобки (3) Скобки (4) Сообщение Строки Фибоначчи
Скобки (3)
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 03/07/2006 | Лето 2006 дорешивание (10D) |
| 26/07/2006 | Лето 2006 - 10 (D) |
| 07/11/2007 | Занятие 9 (D) |
| 07/10/2014 | Занятие 6 (B) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Определим правильные скобочные выражения так:
- Пустое выражение – правильное.
- Если выражение `S` правильное, то (`S`) и [`S`] также правильные.
- Если выражения `A` и `B` правильные, то и выражение `"AB"` – правильное.
Дана последовательность из скобок "(", ")", "[" и "]". Требуется найти самое короткое правильное выражение, в котором данная последовательность является подпоследовательностью, то есть такое, из которого можно вычеркнуть некоторые символы (возможно, ноль) и получить исходную последовательность, не меняя порядок оставшихся.
Ограничения: исходная последовательность содержит не более 100 скобок.
Ввод
В первой строке находятся символы (, ), [ и ] без пробелов.
Вывод
Выводится искомая последовательность скобок без пробелов.
Пример ввода 1
([(]
Пример вывода 1
()[()]
Пример ввода 2
([[)]]
Пример вывода 2
([[()]])
Пример ввода 3
(([))]
Пример вывода 3
(([]))[]
Пример ввода 4
(([[[))]]]
Пример вывода 4
()()[[[()()]]]
