10331. Отгадай животное
Когда коровам стало скучно играть
в игру ракушки, Бесси и ее подруга Элси любят играть в другую игру, называемую “угадай
животное”.
Первоначально Бесси думает о
каком-то животном (чаще всего это животное – корова, что делает игру довольно
скучной, но иногда Бесси проявляет изобретательность и думает о чем-то другом).
Затем Элси задает серию вопросов, чтобы выяснить, какое животное выбрала Бесси.
Каждый вопрос спрашивает, есть ли у животного какие-то определенные
характеристики, и Бесси отвечает на каждый вопрос “да” или “нет”. Например:
Elsie: “Животное летает?”
Bessie: “нет”
Elsie: “Животное ест траву?”
Bessie: “да”
Elsie: “Животное дает молоко?”
Bessie: “да”
Elsie: “Животное говорит муу?”
Bessie: “да”
Elsie: “В таком случае я думаю,
что это корова.”
Bessie: “Правильно! ”
Назовем “допустимым множеством” набор
всех животных с характеристиками, согласующимися с вопросами Элси. Тогда Элси
продолжает задавать вопросы до тех пор, пока возможный набор не будет содержать
только одно животное, после чего она объявляет это животное в качестве своего
ответа. В каждом вопросе Элси выбирает характеристику какого-нибудь животного
из возможного набора, чтобы спросить о нем (даже если эта характеристика не
сможет помочь ей сузить возможный набор в дальнейшем). Она никогда не
спрашивает дважды об одной и той же характеристике.
Зная всех животных, которых знают
Бесси и Элси, а также их характеристики, определите максимальное количество
ответов “да”, которые Элси могла бы получить, прежде чем она узнает правильное
животное.
Вход. Первая строка содержит
количество животных n (2 ≤ n ≤ 100).
Каждая из следующих n строк описывает одно животное. Строка начинается с
имени животного, затем целого числа k (1 ≤ k ≤ 100),
и k характеристик этого животного. Имена и характеристики животных представляют
собой строки, содержащие до 20 строчных букв (a .. z). Нет двух животных с абсолютно
одинаковыми характеристиками.
Выход. Выведите максимальное количество
ответов “да”, которое Элси могла бы получить до окончания игры.
|
Пример
входа |
Пример выхода |
|
4 bird 2 flies
eatsworms cow 4 eatsgrass
isawesome makesmilk goesmoo sheep 1 eatsgrass goat 2 makesmilk
eatsgrass |
3 |
перебор
Перебором найдем
двух животных с максимальным количеством общих признаков temp. Тогда максимальное количество
ответов “да”, которые может получить Элси, равно temp + 1.
Пример
Корова и коза
имеют два общих признака: makesmilk, eatsgrass. На эти запросы Элси даст ответ “да”. Третьим запросом с ответом “да” будет
запрос о признаке коровы, отличный от этих двух.
Реализация алгоритма
Характеристики животного номер i будем хранить в массиве
ch[i].
vector<string> ch[100];
Функция common вычисляет количество общих признаков для
животных с номерами i и j.
int common(int i, int j)
{
int cnt = 0;
for (int x = 0; x < ch[i].size(); x++)
for (int y = 0; y < ch[j].size(); y++)
if (ch[i][x] == ch[j][y]) cnt++;
return cnt;
}
Основная часть программы. Читаем входные данные.
cin >> n;
for (i = 0; i < n; i++)
{
cin >> s >> k;
for (j = 0; j < k; j++)
{
cin >> s;
ch[i].push_back(s);
}
}
Перебираем все пары животных. Для каждой пары (i, j) вычисляем
количество их общих признаков temp. Среди всех таких значений temp вычисляем
наибольшее значение res.
res = 0;
for (i = 0; i < n; i++)
for (j = i + 1; j < n; j++)
{
temp = common(i, j);
if (temp > res) res =
temp;
}
Выводим ответ.
cout << res + 1
<< endl;