Швидкість Ворп#2624
У недалекому майбутньому космічні інженери можуть винайти нову технологію для подорожей у космосі, яку назвуть "варп-двигун". Цей варп-двигун дозволяє космічному кораблю подорожувати швидше за швидкість світла, згинаючи певну відстань у космосі, що дозволяє кораблю подолати цей зігнутий простір за один "стрибок". Оскільки час, витрачений на кожен стрибок, однаковий, загальний час подорожі для будь-якого космічного корабля (оснащеного цим варп-двигуном) залежить від кількості стрибків, які він здійснює. Крім того, інженери виявили, що відстань стрибка визначається певними типами силових полів, присутніх у місці, де здійснюється стрибок. Щоб подорожувати від початкової до кінцевої точки, космічний корабель може пройти через багато силових полів, що може вимагати багато стрибків.
З їхніх експериментів було виявлено такі факти:
Кількість типів силових полів досить мала.
Тому кожен тип силового поля можна позначити однією англійською літерою.
Космічний корабель може пройти через будь-яке окреме силове поле за один стрибок.
Також космічний корабель може пройти через певні послідовності з двох або більше силових полів за один стрибок. Такі послідовності визначаються як правила для одного стрибка.
Приклад списку цих правил наведений у наступній таблиці.
У цьому прикладі є правила, тобто космічний корабель може пройти через кожне з них за один стрибок. Перше правило — , тобто корабель може пройти через і за один стрибок. Друге — , корабель може пройти через , , і за один стрибок.
Зауважте, що в цьому прикладі немає правила/послідовності , тому, хоча корабель може пройти через послідовність , він не може пройти через за один стрибок. Потрібно зробити стрибки: перший через , а другий через силове поле .
Мета
Припустимо, ви інженер на бойовому космічному кораблі. Ваше завдання — провести свій космічний корабель крізь космос якнайшвидше. Ваш корабель обладнано зондом, який може визначати послідовність силових полів на шляху до пункту призначення. Для виконання завдання створіть комп'ютерну програму, яка за наведеними правилами та довільною послідовністю силових полів знаходить мінімальну кількість стрибків.
Вхід — це стандартне введення, що містить частини, розділені порожнім рядком.
Перша частина — це набір правил для послідовностей, які можна пройти за один стрибок. Кількість правил — від до .
Кожен рядок першої частини містить одне правило.
Кожне правило — підпослідовність силових полів, представлену рядком англійських літер (-, -).
Порядок у кожній підпослідовності — зліва направо.
Довжина підпослідовності — від до .
Друга частина містить послідовності силових полів, які має пройти космічний корабель. Кількість послідовностей — від до .
Кожен рядок другої частини містить одну послідовність силових полів.
Кожну послідовність представлено рядком англійських літер (-, -).
Порядок у кожній послідовності — зліва направо.
Довжина послідовності — від до .
Порожній рядок після другої частини означає кінець введення.
Для кожної послідовності другої частини введення запишіть частини виходу наступним чином:
У першому рядку — загальну кількість рішень, потім пробіл і мінімальну кількість стрибків.
У наступних рядках запишіть кожне рішення окремим рядком. Кожне рішення — це послідовність підрядків за введенням, де між підпослідовностями (стрибками) ставиться пробіл. Якщо рішень декілька, вони мають бути відсортовані в порядку зростання та лексикографічно (ASCII).
Додаткові пояснення
У прикладі правил і вхідних послідовностей.
- У першому прикладі виходу — рішення з стрибками. Перший стрибок із першого правила. - У другому виході — рішення з стрибком, використовуючи друге правило для послідовності повністю. - У третьому виході — рішення з стрибками. Перше — з -го правила, друге — з -го правила. - У четвертому виході — рішення з стрибками. Перше рішення використовує -те правило двічі. Друге і третє використовують -тє і -те правила в різних позиціях. Останнє рішення використовує -тє правило двічі. Останній вихід схожий на четвертий, але з п'ятим правилом у середині послідовності.
Приклад 1