Дужкова інверсія
Обмеження: 2 сек., 512 МіБ
Якщо ми не можемо знайти рішення, це не означає, що його не існує.
Ендрю Вайлс
Петрик успішно впорався з минулим завданням, але через те, що ледве встиг вчасно здати його, одразу ж отримав нове - створити програму, яка перевіряє коректність послідовності дужок, а ще, окрім цього, пропонує способи вирішення проблеми, якщо послідовність не є коректною.
Послідовність дужок вважаємо коректною, якщо вона відповідає наступним умовам:
Пуста послідовність завжди коректна.
Якщо
S- коректна послідовність, то(S)- теж коректна послідовність.Якщо
SтаT- коректні послідовності, то і їх конкатенаціяST- теж коректна послідовність. Наприклад, конкатенація()та(())- це()(()).
Таким чином, (), (()) та ()()
- коректні послідовності, а (,((),
)))( - ні.
Ідея Петрика щодо способу вирішення вищеописаної проблеми полягає в
наступному (назвемо це інверсією): програма обирає індекси
\(l\) та \(r\) \((1 \leq l
\leq r \leq n)\), де \(n\) -
довжина послідовності дужок, та намагається замінити кожну з дужок на
цьому інтервалі на протилежну - ( на ) та
навпаки.
Нехай Петрик і придумав ідею, але не придумав реалізацію перевірки на те, чи можливо це зробити на даній послідовності дужок, і просить вас це зробити за нього.
Блоки тестів
Блок 1: 3 бали, \(1 \leq n \leq 3\).
Блок 2: 9 балів, рядок складається виключно з дужок одного типу (тобто лише
(або)).Блок 3: 48 балів, \(1 \leq n \leq 100\).
Блок 4: 40 балів, без додаткових обмежень.
Вхідні дані
У першому рядку задано рядок \(s\) —
послідовність дужок ( та ) довжини \(n\).
Вихідні дані
В єдиному рядку виведіть possible, якщо існує така
інверсія заданої послідовності, що після неї послідовність стане
коректною, інакше виведіть impossible.
Обмеження
\(1 \leq n \leq 5000\)
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| ())) | possible |
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| )((( | impossible |
Примітки
У першому прикладі маємо ми можемо взяти \(l = 3\), \(r =
3\), застосувати на цьому відрізку інверсію і з ()))
отримаємо ()(), що є коректною послідовністю дужок.
У другому прикладі не існує жодного способу застосувати інверсію таким чином, щоб ця послідовність дужок стала коректною.
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|