|Online Judge||Problem Set||Authors||Online Contests||User|
The following scenario takes place between 8:00AM and 9:00AM. In the headquarters of the Counter Terrorist Agency (CTA), you are tasked to aid Jack prevent the next terror attack. The CTA has been tracking the terrorists for over a week. It was discovered that the terrorists operate in separate independent groups. Each group carries a specific chemical which is harmless by itself. Though it is not readily available, possession of such chemical even in huge quantity is not illegal. Thus these groups cannot be apprehended even if they are spotted in possession of the chemical. However, if the groups meet in the same city, they can mix the chemical that they have at hand and form a nerve agent, which they can release within the next hour.
To track down and prevent the next attack, it was determined that all groups move independently of each other using forward then left protocol in 16 cities as shown in Figure 3. The protocol means forward to the next city followed by the city on the left. In the case when there is no city in front, the group heads to the next city to the left. If there is no city to the left, the group backtracks to the previous city. In both cases, the move in the protocol is skipped, as it is replaced by the alternate movement. If there are no cities to backtrack into, (e.g. if there is no information on its previous location) the group stay put in the city and simply wait it out.
The attack is carried out only when all groups meet in the same city. Figure 3 illustrates a map of the cities, where each city is labelled using x, y coordinates. Moving forward implies maintaining the same direction from previous to current. For example, if the group is currently at city 3,3 and previously at 4,3 moving forward means going to 2,3, if the group is previously at 3,4, then the group moves to 3,2; if the group is previously at 2,3, then it proceeds to 4,3 and if previously at 3,2, the group goes to 3,4.
A left implies moving counterclockwise based on the current and previous location. For example, if the group is currently at city 3,3 and previously at 4,3 moving left means going to 3,4; if the group is previously at 3,4 then the group goes to 2,3; if the group is previously at 3,2, the group moves to 4,3; and if the groups is previously at 2,3, it proceeds to 3,2.
It was also learned that all groups can move from one city to the next city in exactly 20 minutes. Since the group cannot be apprehended if they are carrying only the single chemical, they have to be apprehended in the act of preparing the nerve agent. Since you lack man power to track all groups simultaneously, you are tasked to determine the time and place all groups will meet to prepare the nerve agent.
Satellite tracking can only show the whereabouts of each group at the start of the hour. Time is running out fast. When and where should you send Jack to take down these terror groups? However, if all groups were not able to meet within 24 hours, the threat alert level is dropped, as the terrorist will disband and decide on the next attack sometime in the future.
The input will contain several test cases. The first line will indicate the number of test cases. Each test case starts with the number of terror groups moving about the 16 cities. Then it is followed by the coordinate values x and y of each group taken at the start of the hour followed by the next direction either forward (F) or left (L) that they will be initially moving. For the initial movement, we will assume that a forward is a decrease in the y coordinate and a left is a decrease in the x coordinate value.
The output must show in which city all the groups will meet and the time (24-hour time format) in which Jack must be situated to take down the terrorist. Otherwise, it outputs a plain text stating "no terror threat" if the groups do not converge within 24 hours.
1 2 2, 3, F 3, 4, F
Case 1: 1, 3, 900
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator