BIRD - Bird or not bird

You are studying animals in a forest, and are trying to determine which animals are birds and which are not.


You do this by taking two measurements of each animal – their height and their weight. For an animal to be a bird, its height needs to be within some range, and its weight needs to be within another range, but you're not sure what the height and weight ranges are. You also know that every animal that satisfies these ranges is a bird.


You have taken some of the animals you have measured and shown them to biologists, and they have told you which are birds and which are not. This has given you some information on what the height and weight ranges for a bird must be. For the remaining animals, your program should determine if they are definitely birds, definitely not birds, or if you don't know from the information you have.


Input
One line containing an integer C, the number of test cases in the input.
For each of the C test cases:
• One line containing an integer N, the number of animals you have shown to the
biologists.
• N lines, one for each of these animals, each of the format "H W X", where H is the height
of the animal, W is the weight of the animal, and X is either the string "BIRD" or "NOT
BIRD". All numbers are positive integers.
• One line containing an integer M, the number of animals you have not shown to the
biologists.
• M lines, one for each of these animals, each of the format "H W", where H is the height
of the animal and W is the weight of the animal. All numbers are positive integers.


Output
For each of the C test cases:
• One line containing the string "Case #X:" where X is the number of the test case, starting
from 1.
• M lines, each containing one of "BIRD", "NOT BIRD", or "UNKNOWN" (quotes are
just for clarity and should not be part of the output).


Limits
1 <= C <= 20
1 <= all heights and weights <= 1000000
1 <= N <= 1000
1 <= M <= 1000

Sample input
3
5
1000 1000 BIRD
2000 1000 BIRD
2000 2000 BIRD
1000 2000 BIRD
1500 2010 NOT BIRD
3
1500 1500
900 900
1400 2020
3
500 700 NOT BIRD
501 700 BIRD
502 700 NOT BIRD
2
501 600
502 501
1
100 100 NOT BIRD
3
107 93
86 70
110 115


Sample output
Case #1:
BIRD
UNKNOWN
NOT BIRD
Case #2:
UNKNOWN
NOT BIRD
Case #3:
UNKNOWN
UNKNOWN
UNKNOWN


Được gửi lên bởi:sieunhan
Ngày:2009-11-29
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET
Nguồn bài:Google Code Jam - ACM Vietnam Practice

hide comments
2016-09-27 03:16:36
Code AC:
http://shink.in/Rqoyd
2012-06-22 07:59:47 2ez
AC
2012-06-21 01:37:49 hiepsieunhan
sao de kho hieu qua ?! ca? test vD nua~ hjx ??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.