Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
sharada
Умеете придумывать ребусы и шарады? Отлично. Вам придётся научить этому ремеслу компьютер.
Рассмотрим самый простой тип шарад. Слово, которое надо "зашарадить", составляют из нескольких слов, из которых могут быть вычеркнуты некоторые буквы. Например, ШАРАДА - это, например ШАР без вычёркиваний и ПАНДА без первой и третьей буквы, а РЕБУС - это, к примеру, РЕЯ без последней буквы и БРУС без второй. Порядок букв менять нельзя!
Программа, которую вам предстоит написать, получает слово, которое следует зашарадить, количество слов в базе и сами эти слова. Программа должна собрать слово из наименьшего количества слагаемых из базы. При этом количество вычёркиваемых букв не имеет значения, и одно слово можно использовать многократно (КУСТ можно собрать из трёх слагаемых - трёх экземпляров слова СТУК, если в базе нет иных вариантов). Вывести программа должна минимальное количество слов-слагаемых, из которых можно собрать заданное слово.
Входные данные. В первой строке - слово, которое нужно составить из слов базы с вычеркнутыми буквами. В следующей строке - натуральное число N, не превышающее 1000 - количество слов в базе. В следующих N строках слова базы по одному в строке. Все слова состоят только из строчных букв латиницы, длина исходного слова и слов базы не более 50 символов.
Выходные данные. Одно целое число, минимальное возможное количество слагаемых из базы, из которых можно составить заданное слово. Если слово составить невозможно, програма должна вывести -1.
Пример. При вводе следующих данных
october
6
spring
outumn
winter
pocket
cat
cobra
программа должна вывести 3: такой результат можно получить, использовав слова pOCeT, cOBra и wintER.
Для отправки решений необходимо выполнить вход.
|