Задача A. Вспомогательный вопрос Вселенной ≡
| Автор: | ACM ICPC 2009-2010, NEERC, Northern Subregional Contest | Ограничение времени: | 3 сек | |
| Входной файл: | auxiliary.in | Ограничение памяти: | 256 Мб | |
| Выходной файл: | auxiliary.out |
Условие
Как вы возможно знаете, ученые уже нашли Главный вопрос жизни, Вселенной и вообще, и он таков: "Сколько будет шестью девять?". Не удовлетворившись этим, ученые наняли маленькую Магратеанскую фирму построить мини-компьютер, чтобы найти какой-нибудь более узкий вопрос (они назвали его вспомогательным), который теоретически может пролить свет на жизнь, Вселенную и что-нибудь еще.
Этот компьютер построили, но к сожалению результат вычисления был поврежден и частично потерян.
Наконец, создателям компьютера удалось получить строку,
которая является частью правильного вопроса.
После тщательного анализа, конструкторы подумали, что исходный результат может быть построен из
строки добавлением к ней некоторых букв без перестановки и удаления исходных букв.
Они также полагают, что правильный результат — это арифметическое выражение
(как и Главный вопрос), но поскольку вопрос вспомогательный, он не содержит умножения, только сложение.
Более точно, он должен соответствовать грамматике на рисунке.
Помогите им дать что-нибудь своим клиентам. Они попросили вас восстановить вопрос на основе поврежденного ответа компьютера, который им удалось получить.
Формат входного файла
Входной файл содержит только одну строку — поврежденный вспомогательный вопрос. Это не пустая строка не более чем из 1000 символов. Строка содержит лишь символы "+", "(", ")", и "0", …, "9".Формат выходного файла
Выведите восстановленный вспомогательный вопрос. Гарантируется, что существует правильный вопрос из менее чем 5000 символов и ваше решение должно также быть короче. Если есть более одного решения, выведите любое из них.Примеры тестов
| № | Входной файл (auxiliary.in) |
Выходной файл (auxiliary.out) |
|---|---|---|
| 1 |
|
|
| 2 |
|
|
| 3 |
|
|