НачалоПодразделы
Другие разделы
Дата и время
16/11/2024 23:22:27
Занятие 9
D. Скобки
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 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
()()[[[()()]]]
