947 . Tracking Robots
Description
Several robots are moving around in an area, sending their locations to a server. Receiving a stream of locations sent by
the robots, the server needs to find out the number of robots present in the area.
Assume that the area is a closed polygon, partitioned into some non-overlapping regions labeled 1,…,N. All robots are
initially located in region 1. They all start moving around in the scene. When a robot enters a new region, it sends the
region’s label to the server. Note that each robot can enter and leave any region multiple times.
The server receives one long stream of region labels, without knowing the identity of the sender robots. Knowing the
stream and the area’s map, it needs your help to figure out the number of robots present in the area.
Your task is to find out the minimum and the maximum number of robots that may have created such a
stream, assuming that each robot has at least once sent a region label to the server.
Input Format
There are multiple test cases in the input. The first line of each test case starts with N (1 <= N <= 500), the number of regions, followed by M (1 <= M <= 700), the length of the server's stream. Each of the next N lines describes one region; the i-th
line describes the region i. It starts with ci , which is the number of regions adjacent to region i. ci increasing integers
follow, indicating the labels of those regions. The last line is the server's stream which contains M region numbers, in the same order they were received by the server. The input terminates with a line containing "0 0".
Output Format
For each test case write a single line containing the minimum and maximum possible number of robots present in the
area.
Sample Input 1
4 5 2 2 3 3 1 3 4 3 1 2 4 2 2 3 2 3 4 3 2 0 0
Sample Output 1
1 4
Hints
Problem Source
Migrated from old NTUJ.
2009Tehran
Subtasks
| No. | Testdata Range | Score |
|---|