10331. Guess the animal

When the cows get bored of playing the “shell game”, Bessie and her friend Elsie like to play another game – “guess the animal”.

First, Bessie thinks of some animal (most of the time it's a cow, which makes the game rather dull, but sometimes Bessie gets creative and picks something else). Then Elsie asks a series of yes-or-no questions to figure out which animal Bessie has in mind. Each question concerns whether the animal has a certain characteristic, and Bessie answers each one with “yes” or “no”. For example:

Elsie: "Does the animal fly?"

Bessie : "no"

Elsie : "Does the animal eat grass?"

Bessie : "yes"

Elsie : "Does the animal give milk?"

Bessie : "yes"

Elsie : "Does the animal say 'moo'?"

Bessie : "yes"

Elsie : "In that case, I think it’s a cow."

Bessie : "Correct!"

Let us call a feasible set the set of all animals whose characteristics are consistent with Bessie's answers to Elsie’s questions. Elsie continues asking questions until the feasible set contains exactly one animal, at which point she declares that animal as her answer.

Each time, Elsie chooses the next question by picking some characteristic belonging to an animal in the current feasible set – even if that question might not necessarily help her narrow down the options further. She never asks about the same characteristic twice.

Given all the animals known to Bessie and Elsie, along with their characteristics, determine the maximum number of “yes” answers Elsie could possibly receive before she correctly guesses the animal.

Input. The first line contains an integer n (2 ≤ n ≤ 100) – the number of animals. Each of the following n lines describes one animal. A line begins with the animal’s name, followed by an integer k (1 ≤ k ≤ 100) – the number of its characteristics, then  characteristics themselves.

Animal names and characteristics are strings of lowercase Latin letters (a .. z) with lengths up to 20. No two animals have exactly the same set of characteristics.

Output. Print one integer – the maximum number of “yes” answers Elsie could receive before the game ends.

Sample input	Sample output
4 bird 2 flies eatsworms cow 4 eatsgrass isawesome makesmilk goesmoo sheep 1 eatsgrass goat 2 makesmilk eatsgrass	3

SOLUTION

full search

Анализ алгоритма

Перебором найдем двух животных с максимальным количеством общих признаков 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;