Guess the Animal

题目描述

当玩腻了平时的贝壳游戏时，奶牛 Bessie 和她的朋友 Elsie 喜欢玩另一个常见游戏，叫做“猜动物”。 一开始，Bessie 会想一个动物（大多数时候她想到的都是奶牛，使得游戏相当无聊；但偶尔 Bessie 也会有创意，想点别的）。接着 Elsie 会提出一系列问题来弄清 Bessie 选了什么动物。每个问题都会询问该动物是否具有某种特定特征，Bessie 对每个问题回答“yes”或“no”。例如： Elsie: “Does the animal fly?” Bessie: “No” Elsie: “Does the animal eat grass?” Bessie: “Yes” Elsie: “Does the animal make milk?” Bessie: “Yes” Elsie: “Does the animal go moo?” Bessie: “Yes” Elsie: “In that case I think the animal is a cow.” Bessie: “Correct!”

如果我们把“可行集合”定义为所有与 Elsie 目前为止问题答案一致的动物集合，那么 Elsie 会不断提问，直到可行集合只包含一种动物为止，此时她宣布该动物作为答案。 在每次提问中，Elsie 会从可行集合中的某个动物挑选一个特征来询问（即使这个特征可能并不能进一步缩小可行集合）。她从不对同一个特征问两次。

给定 Bessie 和 Elsie 所知道的所有动物及其特征，请你确定：在 Elsie 知道正确动物之前，她最多可能收到多少次“yes”回答。

输入格式

第一行输入为动物数量 $N$（$2 \leq N \leq 100$）。接下来的 $N$ 行每行描述一种动物。 每行以动物名称开头，然后是一个整数 $K$（$1 \leq K \leq 100$），再接着是该动物的 $K$ 个特征。动物名称和特征均为长度不超过 20 的小写字符串（a..z）。任意两种动物不可能拥有完全相同的特征集合。

输出格式

请输出在游戏结束之前，Elsie 可能收到的“yes”回答的最大数量。

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

3

提示

在这个例子中，Elsie 可以得到一份包含 3 次“yes”回答的对话记录（如上所示），并且不可能得到超过 3 次“yes”回答的对话记录。 题目来源：Brian Dean

标签: USACO|2019|Bronze

来源

USACO|2019|Bronze