Задача D. Время желаний
Задачу добавил: alef
Успешно сдано решений: 5
Выбрать дистрибутив — это, как оказалось, не самая большая проблема. А вот подобрать программное обеспечение, которое устроило бы всех...Каждого сотрудника фирмы обязали составить список — какие функции в каком программном обеспечении он использует.
А сотрудникам отдела, где проходит практику Кеша, — составить еще и список свободно распространяемого программного обеспечения с описанием поддерживаемых функций.
Довольно быстро стало понятно, что у пользователей настолько разные требования (к тому же многие писали в список не только имеющиеся и используемые функции,
но и желаемые), что выбрать одну программу, которая бы устроила всех, скорее всего не получится.
У Кеши есть списки пожеланий пользователей. Ваша задача — определить минимальный по включению набор программ, который устроит работников фирмы. Если это невозможно,
найти минимальный по включению набор, который удовлетворит максимальное число пользователей. Минимальность по включению означает, что если из набора исключить
любую программу, то получившийся набор будет уже удовлетворять меньшее множество пользователей. Программа удовлетворяет пользователя, если в ней реализованы все функции,
которые входят в список требований пользователя.
Формат входного файла input.txt
Первая строка — целое число N — количество пользователей.
В следующих N строках идёт описание требований каждого пользователя.
Условимся для простоты обозначать каждую функцию какой-нибудь строчной буквой латинского алфавита (например, copy - 'c', cut - 'x', paste - 'v').
Тогда список требований задаётся некоторой последовательностью букв (например, copy, cut и paste - "cxv").
Таким образом, каждая из данных N строк представляет собой некоторое слово из не более чем 26 различных строчных латинских букв.
Далее идёт строка с целым числом S - количеством найденных свободно распространяемых программных продуктов.
Следующие S строк содержат описания функций, предоставляемых программами, в том же формате.
Гарантируется, что 1 <= N, S <= 1000.
Формат выходного файла output.txt
Первая строка — два целых числа P и L через пробел — количество выбранных программных продуктов и количество пользователей, для которых не нашелся программный продукт
Следующие P строк содержат номера выбранных программных продуктов (по одному на строке).
Если решений несколько, выведите то, которое вам больше нравится.
Пример входного файла
5
c
x
v
cx
xv
3
c
cx
cxv
Пример выходного файла
1 0
3