Məsələlər
Гадание на словах
Гадание на словах
Всем давно известно, что гадальные автоматы зачастую придумывают истории для того, кто бросил в него монетку. Конечно, иногда бывает и так, что предсказание сбывается.
Компания "\textit{Mocrosoft--Fortune}" решила разработать новый гадальный автомат. Пользователь называет два слова \textbf{A} и \textbf{B}, а затем автомат из букв этих слов составляет третье слово -- \textbf{C}, являющееся результатом гадания. Причем буквы из слова \textbf{A} и из слова \textbf{B} встречаются в слове \textbf{С} в том же порядке, что и в самих словах \textbf{A} и \textbf{B}. Гадальная машина берет буквы из \textbf{A} и \textbf{B} в таком порядке, что буквы в новом слове \textbf{C} получаются максимально упорядоченными. То есть две рядом стоящие буквы в \textbf{C} идут в убывающем порядке как можно реже. Помогите программистам компании "\textit{Mocrosoft--Fortune}".
Вам даны два слова \textbf{A} и \textbf{B}, состоящие из прописных букв латинского алфавита \textbf{\{a, b, …, z\}}. В слово \textbf{A} необходимо вставить буквы слова \textbf{B} так, чтобы при этом порядок следования букв слова \textbf{B} сохранился. При этом количество убывающих (по алфавиту) пар двух рядом стоящих букв полученного слова \textbf{C} должно быть минимально.
\textit{\textbf{Примечание:}} Для примера возьмем \textbf{A} = "\textbf{opq}" и \textbf{B} = "\textbf{leti}", тогда оптимальным предсказанием будет \textbf{C} = "\textbf{LopqETI}". Здесь "\textbf{lopq}" и "\textbf{et}" -- идут по неубыванию в соответствии с алфавитом, но "\textbf{qe}" и "\textbf{ti}" - две пары в убывающем порядке.
\InputFile
Во входном файле в первой строке задано слово \textbf{A}, затем во второй строке задано слово \textbf{B}. Длины слов \textbf{A} и \textbf{B }находятся в пределах от \textbf{1} до \textbf{100}.
\OutputFile
В первой строке выведите количество пар в новом слове \textbf{C}, которые идут в убывающем порядке. Это количество должно быть минимально возможным.
Во второй строке выведите полученное слово \textbf{C}. Для наглядности, буквы слова \textbf{B} выведите заглавными буквами. Если оптимальных решений несколько, то выведите любое.
Giriş verilənləri #1
a b
Çıxış verilənləri #1
0 aB