images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
19/04/2024 07:34:51

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

1782. Уравнение

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Программист Вова давно интересуется различными задачами со строками. В этой задаче будем считать, что строка – произвольная последовательность ASCII-символов c кодами от 33 до 126. Недавно Вова узнал об операциях со строками:
  • сложение строк, обозначается символом +. Например, Doctor+Who=DoctorWho.
  • умножение строк, обозначается символом *. Если `S\ =\ A*B`, то `S\ =\ a_1+B+a_2+B+…+a_n+B`,
    где `a_i` – `i`-ый символ строки `A` (нумерация символов строки начинается с 1). Например,
    aca*x=axcxax.
После этого Вова подумал: почему бы не придумать уравнения, где неизвестной величиной будет строка. После чего Вова стал решать придуманные им уравнения.
Перейдем к формальным определениям. Назовем уравнением последовательность `s_1\ $\ s_2\ \ …\ $\ s_n\ =\ r`, где `s_i` – либо неизвестная строка (обозначается ?), либо какая-то определенная непустая строка (записывается символами строки без каких-либо дополнительных символов или ограничителей), `r` – какая-то определенная непустая строка, а на местах значков `$` могут стоять знаки операций сложения или умножения (причем в разных местах могут стоять разные знаки). Все действия выполняются строго слева направо. Скобки не влияют на приоритет выполнения операций. Гарантируется, что существует единственное `i` такое, что `s_i\ =` ?. Символы ?, +, *, = не используются как символы известных строк. Также всем `s_i` и `r` соответствуют непустые строки.
Требуется решить уравнение подобного вида, если известно, что существует непустое решение.
В первой строке находится строка `S`, задающая уравнение. Количество операций не превосходит 200000, длина строки `S` не более чем 300000 символов. В уравнении всегда присутствует ровно один знак ?.
Напечатайте значение неизвестной строки.

Пример ввода

ab*?+ab=aabbababbaab

Пример вывода

abba
Источник: Московская открытая олимпиада школьников по программированию, 2011/12 учебный год
loading