RiseOJ – 동물 맞히기

설명

소 베시와 친구 엘시는 늘 하던 야바위 게임이 지겨워지면, "동물 맞히기"라는 또 다른 흔한 게임을 즐겨 한다.

먼저 베시가 어떤 동물을 하나 떠올린다 (대부분의 경우 그 동물은 소라서 게임이 꽤 지루해지지만, 가끔 베시는 창의력을 발휘해 다른 것을 떠올리기도 한다). 그러면 엘시는 베시가 고른 동물이 무엇인지 알아내기 위해 일련의 질문을 던진다. 각 질문은 그 동물이 어떤 특정한 특징을 가지고 있는지 묻는 것이고, 베시는 각 질문에 "예" 또는 "아니오"로 답한다. 예를 들면 다음과 같다.

엘시: "그 동물은 날 수 있어?"
베시: "아니"
엘시: "그 동물은 풀을 먹어?"
베시: "응"
엘시: "그 동물은 우유를 만들어?"
베시: "응"
엘시: "그 동물은 음매 하고 울어?"
베시: "응"
엘시: "그렇다면 그 동물은 소인 것 같아."
베시: "정답!"

지금까지 엘시의 질문들과 모순되지 않는 특징을 가진 모든 동물의 집합을 "가능 집합"이라고 부르면, 엘시는 가능 집합에 동물이 하나만 남을 때까지 계속 질문을 하고, 그 후 그 동물을 자신의 답으로 발표한다. 각 질문에서 엘시는 가능 집합에 속한 어떤 동물의 특징 하나를 골라 물어본다 (그 특징이 가능 집합을 더 좁히는 데 도움이 되지 않더라도 상관없다). 같은 특징에 대해 두 번 묻지는 않는다.

베시와 엘시가 알고 있는 모든 동물과 그 특징들이 주어질 때, 엘시가 정답 동물을 알아내기 전까지 받을 수 있는 "예" 대답의 최대 개수를 구하여라.

출제자: Brian Dean

제약

출제자: Brian Dean

입력 형식

입력의 첫째 줄에 동물의 수 $$N$$ ( $2 \leq N \leq 100$ )이 주어진다. 다음 $$N$$ 개의 줄에는 각각 동물 하나에 대한 정보가 주어진다. 각 줄은 동물의 이름으로 시작하고, 그다음 정수 $$K$$ ( $1 \leq K \leq 100$ ), 그다음 그 동물의 특징 $$K$$ 개가 주어진다. 동물의 이름과 특징은 최대 20개의 소문자 (a..z)로 이루어진 문자열이다. 특징들이 완전히 같은 두 동물은 존재하지 않는다.

출력 형식

게임이 끝나기 전까지 엘시가 받을 수 있는 "예" 대답의 최대 개수를 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 guess.in · 출력을 쓸 파일 guess.out

예제 1

입력

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

출력

설명

In this example, it is possible for Elsie to generate a transcript with 3 "yes"
answers (the one above), and it is not possible to generate a transcript with
more than 3 "yes" answers.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2018-2019 > January > Bronze

올림피아드 > USACO > 2018-2019 > January > Bronze

태그

JudgeUSACO

동물 맞히기

평가 및 의견

풀이 제출