Гадання на словах#4899
Відомо, що автомати для ворожіння складають історії для тих, хто опускає монету. Іноді ці передбачення навіть справджуються.
Компанія "Mocrosoft–Fortune" розробляє новий автомат для ворожіння. Користувачі вводять два слова та , і автомат генерує третє слово як результат пророцтва. Це слово складається з букв та з дотриманням порядку букв у початкових словах. Машина розташовує ці букви так, щоб послідовність у була впорядкованою наскільки це можливо, мінімізуючи кількість сусідніх пар букв у спадному алфавітному порядку. Допоможіть програмістам "Mocrosoft–Fortune" досягти цієї мети.
Вам дано два слова і , які складаються з великих латинських літер \{\mathbf{A}, \mathbf{B}, \ldots, \mathbf{Z}\}. Ваше завдання — вставити літери слова у слово , зберігаючи порядок літер у . Мета полягає в тому, щоб мінімізувати кількість спадних (за алфавітом) сусідніх пар літер у результатному слові .
Приклад: Нехай A = \mathbf{opq} і B = \mathbf{leti}. Оптимальне пророцтво буде C = \mathbf{LopqETI}. Тут та розташовані у невисхідному алфавітному порядку, а і утворюють дві спадні пари.
Вхід складається з двох рядків: у першому — слово , у другому — слово . Довжини обох слів і знаходяться в межах від до .
У першому рядку виведіть кількість спадних пар у новому слові , причому цю кількість слід мінімізувати. У другому рядку виведіть саме слово , причому літери зі слова мають бути у верхньому регістрі. Якщо існує декілька оптимальних рішень, дозволяється вивести будь-яке з них.
Приклад 1