#P9960. [USACO19JAN] Guess the Animal B

[USACO19JAN] Guess the Animal B

题目描述

奶牛 Bessie 和她的朋友 Elsie 厌倦了她们的坚果壳游戏,她们想要玩另一个叫做“猜动物”的常见游戏。

游戏开始时,Bessie 会想好一种动物(大部分时候,她想的都是奶牛,这使得游戏相当无聊,但是偶尔 Bessie 也能有些新意,想一些别的)。随后 Elsie 会通过问一些问题来猜出 Bessie 选择的动物。每个问题都是询问这种动物是否具有某个特定的特征,Bessie 对于每个问题回答“是”或“不是”。例如:

Elsie:“这种动物是能飞的吗?”
Bessie:“不是。”
Elsie:“这种动物是吃草的吗?”
Bessie:“是。”
Elsie:“这种动物是能产奶的吗?”
Bessie:“是。”
Elsie:“这种动物是会哞哞叫的吗?”
Bessie:“是。”
Elsie:“这样的话我想这种动物是奶牛。”
Bessie:“猜对了!”

如果我们将所有具备符合 Elsie 到目前为止所提出的问题的特征的动物的集合称为“可行集”,那么 Elsie 会持续进行提问直到可行集仅包含一种动物,然后她会把这种动物作为她的答案。对于每个问题,Elsie 会选择某种动物的一个特征进行询问(即使这个特征并不能进一步帮助她缩小可行集)。她不会关于同一个特征询问两次。

给定 Bessie 和 Elsie 知道的所有动物以及它们的特征,请求出 Elsie 在猜出正确的动物之前能够得到的“是”的回答的最大数量。

输入格式

输入的第一行包含动物的数量 NN2N1002\le N\le 100)。以下 NN 行每行描述了一种动物。每一行开始是这种动物的名称,接下来是一个整数 KK1K1001\le K\le 100),接下来是这种动物的K个特征。动物的名称和特征是至多 2020 个小写字母(a..z)组成的字符串。没有两种动物具有完全相同的特征。

输出格式

输出游戏结束之前 Elsie 可能得到的“是”的回答的最大数量。

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

提示

样例解释 1

在这个例子中,Elsie 可能在对话中获得 33 个“是”的回答(题目中的例子),并且不可能进行包含超过 33 个“是”的回答的对话。