Гадание на словах
Всем давно известно, что гадальные автоматы зачастую придумывают истории для того, кто бросил в него монетку. Конечно, иногда бывает и так, что предсказание сбывается.
Компания "Mocrosoft–Fortune" решила разработать новый гадальный автомат. Пользователь называет два слова A и B, а затем автомат из букв этих слов составляет третье слово – C, являющееся результатом гадания. Причем буквы из слова A и из слова B встречаются в слове С в том же порядке, что и в самих словах A и B. Гадальная машина берет буквы из A и B в таком порядке, что буквы в новом слове C получаются максимально упорядоченными. То есть две рядом стоящие буквы в C идут в убывающем порядке как можно реже. Помогите программистам компании "Mocrosoft–Fortune".
Вам даны два слова A и B, состоящие из прописных букв латинского алфавита {a, b, …, z}. В слово A необходимо вставить буквы слова B так, чтобы при этом порядок следования букв слова B сохранился. При этом количество убывающих (по алфавиту) пар двух рядом стоящих букв полученного слова C должно быть минимально.
Примечание: Для примера возьмем A = "opq" и B = "leti", тогда оптимальным предсказанием будет C = "LopqETI". Здесь "lopq" и "et" – идут по неубыванию в соответствии с алфавитом, но "qe" и "ti" - две пары в убывающем порядке.
Входные данные
Во входном файле в первой строке задано слово A, затем во второй строке задано слово B. Длины слов A и B находятся в пределах от 1 до 100.
Выходные данные
В первой строке выведите количество пар в новом слове C, которые идут в убывающем порядке. Это количество должно быть минимально возможным.
Во второй строке выведите полученное слово C. Для наглядности, буквы слова B выведите заглавными буквами. Если оптимальных решений несколько, то выведите любое.