printРабочее место участника

printЗадачи

1391. Номера словами

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Для облегчения запоминания телефонных номеров на некоторых аппаратах на кнопках с цифрами также написаны буквы. Будем считать номер хорошим, если при его наборе можно получить какое-то осмысленное слово (или несколько слов подряд без пробелов), взяв любую букву с первой нажатой кнопки, затем любую со второй и т.д.
Городские номера у нас имеют 6 цифр. В этой задаче будем считать, что номер может быть последовательностью любых 6 цифр (в том числе с ведущими нулями). Дан словарь, в котором все слова имеют длину от 1 до 6 букв. Также известно размещение букв на кнопках телефонного аппарата. Требуется определить, сколько телефонных номеров может быть представлено словами или цепочками слов из этого словаря (в цепочке слова могут повторяться).
Первые десять строк входного файла описывают размещение букв на кнопках. В первой строке находится цифра 0 и через пробел строка из назначенных ей букв (буквы записаны без пробелов), во второй строке стоит цифра 1, пробел и её буквы и так далее до цифры 9 включительно. Возможно, что каким-то кнопкам ни одной буквы не назначено – в строке, соответствующей этой кнопке, стоит цифра, за которой следует один пробел.
В следующей строке записано число `N` от 1 до `10 000` –количество слов в словаре. Далее следует `N` строк, каждая строка содержит одно слово, записанное строчными латинскими буквами.
Выведите в первой строке выходного файла одно число – найденное количество номеров.

Пример ввода

0 abqw
1 cery
2 dt
3 fgh
4 ijk
5 lmn
6 op
7 su
8 
9 vxz
3
abc
cde
qwerty

Пример вывода

4
Источник: XIII Межвузовская олимпиада, г. Вологда, 2010
loading