Темы --> Информатика --> Язык программирования
    Процедуры и функции(96 задач)
    Массивы(232 задач)
    Типы данных(356 задач)
    Циклы(177 задач)
    Условный оператор (if)(164 задач)
    Python(260 задач)
    Standard Template Library(2 задач)
---> 2 задач <---
Источники --> Личные олимпиады --> COCI --> COCI 2015-2016 --> Раунд 2
Страница: 1 Отображать по:
#113553
Гепетто и пицца
  
Темы: [Массивы]
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 2, Гепетто и пицца ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Любимый всем кукольник Гепетто открыл новую пиццерию. Он хочет делать самую лучшую пиццу в городе, но не хочет иметь маленький ассортимент пицц.

Гепетто делает свои пиццы из N ингредиентов, пронумерованных от 1 до N . Всё было бы хорошо, но к сожалению он не может класть некоторые ингредиенты в одну пиццу.

Всего есть M пар ингредиентов, которые нельзя класть в одну пиццу. Помогите Гепетто узнать, сколько различных пицц он может cделать.

Входные данные

Первая строка содержит два целых числа N и M ( 1 ≤ N ≤ 20 , 0 ≤ M ≤ 400 ). Следующие M строк содержат по два различных чсла a и b , обозначающие, что класть ингредиенты a и b запрещено класть в одну пиццу ( 1 ≤ a , b ≤ N ).

Выходные данные

Выведите одно число – ответ на задачу

Примечание

В первом примере Гепетто может сделать пиццы из наборов {}, {1}, {2}, {3}, {1, 3}. Во втором примере он может использовать любую комбинацию ингредиентов. В третьем примере он может сделать пиццы из наборов {}, {1}, {2}, {3}.

Примеры
Входные данные
3 2
1 2
2 3
Выходные данные
5
Входные данные
3 0
Выходные данные
8
Входные данные
3 3
1 2
1 3
2 3
Выходные данные
4
#113558
Телефон Марко
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 2, Телефон Марко ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Марко обнаружил новую функцию на его телефоне - Т9. На его телефоне имеется стандартная клавиатура на 9 кнопок:

Для того чтобы вводить текст на этой клавиатуре необходимо несколько раз нажимать клавишу с соответствующей буквой. Точнее, если это первая буква на клавише, нужно нажать 1 раз, если вторая буква - 2 раза, и так далее. Например, если мы хотим ввести слово "giht", то необходимо нажать клавиши следующим образом: g-4 i-444 h-44 t-8. Новая возможность, которую открыл Марко, упрощает ввод текста, потому что больше не требуется нажимать по одной клавише несколько раз подряд - достаточно всего одного нажатия. Программа будет пытаться понять, какое слово из словаря вы пытаетесь ввести.

Марко довольно скептически относится к новым технологиями (как минимум к новым для него) и он боится, что ошибки будут довольно часто. Марко наизусть знает весь словарь мобильного телефона. Он состоит из N слов, состоящих из строчных латинских букв, длина каждого слова не превышает 1000000 символов. Марко даст массив нажатий на клавиши S длиной не более 1000, и хочет узнать как много слов из словаря он может получить при такой последовательности нажатий если используется функция Т9.

Входные данные

Первая строка содержит единственное целое число N ( 1 ≤ N ≤ 1000 ) - количество слов в словаре. Каждая из следующих N строк содержит одно слово из словаря S i ( 1 ≤ | S i | ≤ 1000000 ). Последняя строка содержит строку S ( 1 ≤ | S | ≤ 1000 ), состоящую из цифр от 2 до 9.

Выходные данные

Выведите единственное целое число - количество слов из словаря, которые можно получить при данной последовательности нажатий.

Примеры
Входные данные
3
tomo
mono
dak
6666
Выходные данные
1
Входные данные
2
ja
la
52
Выходные данные
2
Входные данные
3
dom
fon
tom
366
Выходные данные
2
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест