ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Уральская региональная командная олимпиада по программированию 2013

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

H. Мутанты против машин

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
2031 год. Обещанная точка сингулярности наступила, и компьютеры восстали против людей. Единственная надежда человечества — разумные генетически модифицированные боевые организмы, которые приняли нашу сторону в этом конфликте. Разумеется, машины не останавливаются в развитии и постоянно создают всё более смертоносных роботов. Люди же постоянно ищут новые последовательности ДНК, которые сделают мутантов ещё сильнее и выносливее.
Так, профессор Ерфаломей Бен недавно понял, что силу мутантов можно сравнивать, зная только их последовательности ДНК. Для этого нужно записать последовательности ДНК как строки из маленьких букв латинского алфавита (конечно же, учёным будущего не хватило четырёх азотистых оснований, и они добавили новые). Мутант X сильнее мутанта Y, если последовательность ДНК мутанта X лексикографически меньше последовательности ДНК мутанта Y.
Сейчас профессор хочет провести эксперимент. У него есть ДНК мутанта и набор генных модификаторов — веществ, способных изменять ДНК. Каждый модификатор обозначается маленькой буквой латинского алфавита. Профессор Бен может брать генные модификаторы из набора в любом порядке и выполнять с каждым из них одно из следующих действий.
  1. Вставить генный модификатор в любое место последовательности ДНК (между буквами, либо перед строкой, либо после строки).
  2. Выбрать в последовательности ДНК позицию, на которой стоит буква, совпадающая с генным модификатором. После чего удалить данную букву из последовательности и уничтожить генный модификатор.
При этом у генных модификаторов скоро выходит срок годности, поэтому профессор Бен непременно хочет использовать весь набор. Каким образом он должен сделать это, чтобы получить из ДНК, имеющейся в его распоряжении, ДНК как можно более сильного мутанта?

Исходные данные

В первой строке дана исходная последовательность ДНК. Во второй строке дан набор генных модификаторов. Обе строки непустые, состоят только из маленьких букв латинского алфавита и имеют длину не более 100 000.

Результат

Выведите лексикографически наименьшую последовательность ДНК, которую можно получить из исходной после применения всех генных модификаторов. Гарантируется, что к исходной ДНК нельзя применить все модификаторы так, чтобы получилась пустая строка.

Пример

исходные данныерезультат
abc
bbc
ab
Автор задачи: Илья Кучумов
Источник задачи: Уральская региональная командная олимпиада по программированию 2013
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2007. Мутанты против машин