USACO 2019 January Contest, Bronze3- Guess the Animal > 문제은행 : 정보올림피아드&알고리즘




3538 : Guess the Animal

제한시간
2000 ms   
메모리제한
256 MB   
해결횟수
1 회   
시도횟수
4 회   

문제

베시와 엘시가 동물 이름 맞추기 게임을 하고 있다.

베시가 어떤 동물을 마음속으로 생각한다.

엘시가 동물의 특징을 말한다.

베시는 예 / 아니오 대답을 한다.

 

예를 들어 보자.

엘시 : 날수 있는 동물입니까?

베시 : 아니오

엘시 : 풀을 먹는 동물입니까?

베시 : 예

엘시 : 우유를 만드는 동물입니까?

베시 : 예

엘시 : 'moo'하는 울음 소리를 냅니까?

베시 : 예

엘시 : 소입니다.

베시 : 정답입니다 ^^

 

동물 목록과 각 동물이 특징들이 주어진다.

베시는 주어진 동물목록 중에 한 동물을 마음속으로 생각한다.

주어진 특징들의 목록에서 답으로 가능한 목록들만을 모은 것을 실현가능목록 이라 하자. 

이 실현가능목록으로 결정할 수 있는 동물이 하나로 결정되면 베시는 답을 말한다. 

베시는 같은 질문을 두번 이상 하지 않는다.

답을 구하는데 도움이 되지 않는 질문이라도 주어진 특징을 이용하여 질문할 수 있다.

 

 

 


입력형식

첫 행에 동물의 수 N( 2 <= N <= 100) 이 주어진다. 이후 각 행마다 동물 이름, 특징 수, 특징(들)이 주어진다.

출력형식

베시가 얻을 수 있는 예 라는 대답의 최대값을 구하여 출력한다.

입력 예

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

출력 예

3


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP