새란 무엇인가 (라지)
면접 대비시간 제한5초메모리 제한512 MB
새는 높이 구간과 무게 구간의 교집합에 정확히 들어오는 동물이라는 사실과 일부 표본의 분류 결과가 주어질 때, 나머지 동물 각각이 항상 새인지, 절대 새가 아닌지, 판단할 수 없는지 가린다.
문제
숲에서 동물을 관찰하면서 어떤 동물이 새이고 어떤 동물이 새가 아닌지 가려내려고 한다.
방법은 동물마다 키와 무게를 재는 것이다. 어떤 동물이 새이려면 키가 어떤 구간 안에 들어가고 무게도 또 다른 어떤 구간 안에 들어가야 한다. 두 구간이 정확히 무엇인지는 모른다. 반대로 두 구간을 모두 만족하는 동물은 예외 없이 모두 새다.
측정한 동물 중 일부를 생물학자에게 보여 주었더니, 생물학자가 어느 것이 새이고 어느 것이 새가 아닌지 알려 주었다. 이 답에서 새의 키 구간과 무게 구간이 어떠해야 하는지 일부 정보를 얻는다. 남은 동물에 대해 확실히 새인지, 확실히 새가 아닌지, 아니면 가진 정보만으로는 판정할 수 없는지 결정하는 프로그램을 작성한다.
생물학자의 답은 실제 두 구간에서 나온 것이므로 입력에 모순은 없다. 즉 주어진 모든 답과 들어맞는 키 구간과 무게 구간이 적어도 한 쌍 존재한다.
입력
첫 줄에 테스트 케이스의 개수 가 주어진다.
이어서 개의 테스트 케이스마다 다음이 주어진다.
- 첫 줄에 생물학자에게 보여 준 동물의 수 이 주어진다.
- 다음 개의 줄에 동물 하나씩의 정보가 " " 형식으로 주어진다. 는 키, 는 무게이고, 는 문자열 "BIRD" 또는 문자열 "NOT BIRD"다.
- 다음 줄에 생물학자에게 보여 주지 않은 동물의 수 이 주어진다.
- 다음 개의 줄에 동물 하나씩의 정보가 " " 형식으로 주어진다. 는 키, 는 무게다.
모든 키와 무게는 양의 정수다.
제한
출력
각 테스트 케이스마다 다음을 출력한다.
- 첫 줄에 문자열 "Case #:"를 출력한다. 는 1부터 시작하는 테스트 케이스의 번호다.
- 이어지는 개의 줄에 생물학자에게 보여 주지 않은 동물을 입력에 주어진 순서대로 판정해 출력한다. 답과 들어맞는 모든 구간 쌍에서 항상 새라면 "BIRD", 그런 모든 구간 쌍에서 항상 새가 아니라면 "NOT BIRD", 그 밖의 경우에는 "UNKNOWN"을 출력한다. 큰따옴표는 출력하지 않는다.
힌트
예제의 첫 번째 테스트 케이스에서 키 구간과 무게 구간은 둘 다 1000과 2000을 포함한다. 그래서 키 1500, 무게 1500인 동물은 두 구간 안에 반드시 들어가고, 새다.
키 900, 무게 900인 동물은 판정할 수 없다. 두 구간이 900을 포함하는지 알려 주는 정보가 없다.
키 1400, 무게 2020인 동물은 키 구간 안에 있다. 그런데 무게 구간이 2020을 포함한다면 새가 아니라고 확인된 키 1500, 무게 2010인 동물도 두 구간 안에 들어가 버린다.
두 번째 테스트 케이스에서는 새의 키가 501이어야 한다는 것을 알 수 있다. 무게 구간은 700을 포함한다는 사실 외에는 알 수 없다.
세 번째 테스트 케이스에서는 키 100, 무게 100인 동물이 새가 아니라는 사실만 알 뿐, 새가 어떤 동물인지는 전혀 알 수 없다.