13/04/2025 14:53:50

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

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

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 учебный год

25/06/2012	Лето 2012 - дорешивание ( 7F)
05/07/2012	Лето 2012 - 7 (F)