当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

3362:20-Four

题目描述

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.

Figure 3: Map of 16 cities that all terror groups move about and a group starting at 4,3 with a left.

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

该题目是Virtual Judge题目,来自 北京大学POJ

题目来源 Manila 2006

源链接: POJ-3362

最后修改于 2020-10-29T06:59:40+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
1000 65536