Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Помогие решить Заменить до правильной скобочной последовательности

Ирина Александрова Ученик (84), закрыт 2 недели назад
ограничение по времени на тест1 секунда
ограничение по памяти на тест256 мегабайт
Заменить до правильной скобочной последовательности
ограничение по времени на тест1 секунда
ограничение по памяти на тест256 мегабайт
Вам задана строка s, состоящая из открывающих и закрывающих скобок четырех видов <>, {}, [], (). Все скобки делятся на два типа: открывающие и закрывающие. Разрешается заменить любую скобку на любую другую такого же типа. Например, скобку < можно заменить на скобку {, но нельзя заменить на скобку ) или >.

Далее приводится стандартное определение правильной скобочной последовательности, с которым вы возможно уже знакомы.

Определим правильную скобочную последовательность. Пустая строка считается таковой. Пусть строки s1 и s2 являются правильными скобочными последовательностями, тогда строки <s1>s2, {s1}s2, [s1]s2, (s1)s2 также являются правильными скобочными последовательностями.

Например, строка "[[(){}]<>]" является правильной скобочной последовательностью, а строки "[)()" и "][()()" — нет.

Определите наименьшее количество замен, необходимое для того, чтобы сделать строку s правильной скобочной последовательностью.

Входные данные
Единственная строка содержит непустую строку s, состоящую только из открывающих и закрывающих скобок, заданных четырех видов. Длина строки s не превосходит 106.

Выходные данные
Если получить правильную скобочную последовательность из строки s невозможно выведите слово Impossible.

Иначе выведите наименьшее количество замен, необходимое для получения правильной скобочной последовательности из строки s.

Примеры
Входные данные
[<}){}
Выходные данные
2
Входные данные
{()}[]
Выходные данные
0
Входные данные
]]
Выходные данные
Impossible
Лучший ответ
Андрей Высший разум (451628) 1 месяц назад
Собственно, первую половину алгоритма нейросеть в соседнем ответе написала вполне правильно. Но вот после цикла начала нести бред.
 stack, cnt, sym = [], 0, {'[':']', '{':'}', '(':')', '<':'>'}
for ch in input():
if ch in sym:
stack.append(sym[ch])
elif not stack:
stack.append('@')
break
else:
cnt += ch != stack.pop()
print(['Impossible', cnt][not stack])
Остальные ответы
Sergio 2.1 Оракул (64093) 1 месяц назад
 s = input().strip() 
stack = []
replacements = 0
opening = {'<', '{', '[', '('}
closing = {'>', '}', ']', ')'}
pairs = {'<': '>', '{': '}', '[': ']', '(': ')'}

for char in s:
if char in opening:
stack.append(char)
elif char in closing:
if not stack:
print("Impossible")
exit()
last_open = stack.pop()
if pairs[last_open] != char:
replacements += 1

if stack:
if len(stack) % 2 != 0:
print("Impossible")
else:
replacements += len(stack) // 2
exit()

print(replacements)
Ирина АлександроваУченик (84) 1 месяц назад
мне нужно без функций, мне чат gpt также решил но неверно
ПапаВысший разум (139355) 3 недели назад
Ты после каждого бана становишься 2.0, 2.1 и т.д.?
Похожие вопросы