Birds
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 109
Solved: 13
- Description
- You are learning birds’ theory 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 heights and weights. If an animal is a bird, its height needs to be within a bound, and its weight needs to be within another bound. But you don’t know what the bound of the height or weight are. You also know that every animal which satisfies the bound of the height and weight is a bird.
You have taken some of the animals to the biologists, then they told you which ones are birds and which ones are not. This has given you some information about the bound of the height and weight for a bird, but you still can’t make sure the exactly bound.
For the remaining animals, you must find out that how many of them can be birds at most?
- Input
- The first line contains an integer T means the number of the test cases.
Then for each of the T test cases:
The following one line contains an integer N, the number of animals you have taken to the biologists. The following N lines, every line stands for an animal in the format "H W X", while H is the height of the animal, W is the weight of the animal and X is either a sign "Y" or "N ". If X is “Y”, the animal is a bird; or not.
The following one line contains an integer M, the number of animals you have not taken to the biologists. The following M lines, every line stands for an animal in the format "H W", where H is the height of the animal and W is the weight of the animal.
1 ≤ N ≤ 16, 1 ≤ M ≤ 16, all numbers in the input is a positive integer less than 100,000.
- Output
- For each test case, output one line containing an integer X, which means there are at most X birds in the remaining animals.
- sample input
-
1 5 1000 1000 Y 2000 1000 Y 2000 2000 Y 1000 2000 Y 1500 2010 N 3 1500 1500 900 1000 1400 2020
- sample output
-
2
- hint
- In the sample test case: If (1500, 1500) and (900, 1000) are birds, so the bound of a bird can be {900 <= H <= 2000, 1000 <= W <= 2000}, then (1500, 2010) and (1400, 2020) can’t be birds.
- source