Intelligent Traffic Surveillance
Time limit1sMemory limit128 MB
Replay service logs to recover zone and exemption states and print one penalty ticket per vehicle-day with every violating photo.
- Level
Medium7 of 10
- Topics
- Simulation, Binary search, Implementation, Sorting
- Solved
- No attempts yet
Problem
Tehran's central traffic control office runs a surveillance system that reads plates from camera photos and issues penalty tickets automatically. The storage of its database server then hit a fatal hardware crash and every byte of data was lost. The only surviving information is the log files left on the application server. Every form of data entry passes through the service layer and is logged there, so the lost information can be recovered from the logs alone. Write a program that reads all the log files and issues the penalty tickets.
Every road belongs to one of three zones:
- Central Traffic Restricted Zone (CTRZ)
- Even/Odd Restricted Zone (EORZ)
- Unrestricted Zone (UZ)
An ordinary personal vehicle may not enter CTRZ during these intervals:
- Saturday through Wednesday, 06:30 to 17:00
- Thursday, 06:00 to 13:30
An ordinary personal vehicle whose registration number ends with an even digit may not enter EORZ during these intervals:
- Sunday and Tuesday, 06:30 to 19:00
- Thursday, 06:30 to 17:00
An ordinary personal vehicle whose registration number ends with an odd digit may not enter EORZ on Saturday, Monday and Wednesday from 06:30 to 19:00.
Friday is the official weekend in Iran, so no zone restriction applies on Friday. Both endpoints of an interval count as restricted time. A vehicle photographed at Monday 06:30:00, for example, must be fined.
Some vehicles, including public transport and emergency services, may enter CTRZ and EORZ at any time. An ordinary personal vehicle may also enter after buying a single day permission, but permissions are out of scope here. A vehicle that enters CTRZ or EORZ unlawfully must be fined. Each vehicle is fined at most once a day for zone restriction violations. When a CTRZ violation and an EORZ violation happen for one vehicle on a single day, the ticket is issued for the CTRZ violation, which carries the higher penalty.
Every road starts in UZ, and no vehicle starts exempt from the zone regulations. Announcements change these states, and the new rule of an announcement applies from the day after it. Adding or removing an exempt vehicle applies from the next day in the same way.
The application server provides the services below. Each service has one log message written on a single line, starting with the service name and followed by the parameters in the order given in the service definition. Independent of the service type, the parameter list of every log message starts with a special pair called the timestamp: day and time. A timestamp shows the exact moment of its service request. Parameter day is a nonnegative integer counting the days passed since the deployment day, which is day 0. Parameter time shows the moment of the request on that day in HH:mm:ss format (, ).
setRoadZone(day, time, zone, roads)
Parameter zone is UZ, CTRZ, or EORZ. Parameter roads is a nonempty list of road names that need not be distinct. From the beginning of the next day those roads belong to the given zone, overriding their former zone state. A log line looks like this:
setRoadZone 2 "09:12:53" "CTRZ" "Enghelab" "Sa'di" "Ferdowsi" "Ferdowsi"
setRoadZone 5 "14:32:01" "EORZ" "Resalat"
setRoadZone 12 "00:00:59" "UZ" "Persian_Gulf"
addZoneException(day, time, vehicles), removeZoneException(day, time, vehicles)
Parameter vehicles is a nonempty list of vehicle registration numbers that need not be distinct. From the beginning of the next day the listed vehicles must not be fined for entering CTRZ or EORZ during the forbidden times (addZoneException), or must be fined again (removeZoneException). Both commands override the older state of the listed vehicles, even when the state stays the same. A log line looks like this:
addZoneException 1 "09:00:13" "1234567" "9876543"
removeZoneException 3 "15:33:02" "1234567" "9876345"
addPhotoInfo(day, time, photoId, road, vehicles)
This service is not called from the user interface layer. The external image processing server that analyzes the pictures taken by the surveillance cameras calls it once per photo, when the photo is taken and analyzed. Parameter photoId is a positive integer identifying the analyzed photo. Parameter road holds the name of the road the photo was taken from. The image processing server detects the vehicles in the photo and extracts their registration numbers from their plates, and parameter vehicles provides that list. The list can be empty because a photo might show no vehicle. The timestamp here refers to the moment of taking the photo. A log line looks like this:
addPhotoInfo 18 "03:18:43" 3324249 "Pastor" "6256256" "8888310"
addPhotoInfo 4 "20:47:31" 54 "Mokhberoddoleh,_sar-e_Sa'di"
addPhotoInfo 27 "06:39:14" 112385612 "17-e_shahrivar" "1006016"
You can assume the following:
- Every parameter object has one of these forms. Integers are all nonnegative. Strings are always surrounded with quotation marks ("). A list is always the last parameter and consists of space separated strings through the end of the line.
- A single space separates all tokens, including service names, parameter objects and list members.
- Parameter time in HH:mm:ss format has exactly 8 characters, and each of its three parts has exactly 2 digits, padded with 0 when smaller than 10.
- Road names consist of English letters (lowercase and uppercase), digits, dash (-), underscore (_), dot (.), comma (,), and single quotation mark ('). Road names are nonempty and no longer than 100 characters.
- Every vehicle registration number is a string of exactly 7 digits.
- The same road or vehicle is always referenced with the same string.
- No two timestamps are exactly the same.
- When commands conflict on the same day, the newer command, the one with the bigger timestamp, overrides the older one.
- Service addPhotoInfo is called at most once for each photoId.
- A registration number appears at most once in each photo.
- The system runs for at most 300 days.
Vehicles are fined based on the photo analysis results. A zone entrance ticket is issued at most once a day per vehicle, and all photos of that violation on that day are attached to the ticket. Photo attachments are sorted in ascending order by their times. When a CTRZ entrance and an EORZ entrance happen together for a vehicle, the photos of both violations are attached but the ticket is issued with the CTRZ penalty. The order of printed tickets matters too. Tickets are sorted primarily by vehicle, so that registration numbers appear in lexicographic order, and the tickets of one vehicle are then sorted in ascending order by the day of offence.
Input
The input consists of several test cases. Each test case starts with a line containing the single integer , the total number of lines in the log files (). The second line contains a string followed by two positive integers and . String is one of the words Saturday, Sunday, Monday, Tuesday, Wednesday, Thursday, or Friday, specifying the weekday of the deployment day, day 0. Numbers and are the penalty values for an outlawed entrance to CTRZ and to EORZ respectively, with . Each of the next lines contains a service log in the format specified before. The logs are not sorted in any special order because they are the concatenation result of many log files. Each line has at most 1000 characters. All integers in the input are less than . The input terminates with a line containing 0.
Output
For each test case, print the penalty tickets in the order specified before. Each ticket has a main body and one or more attached photos. Print the main body first, on a single line, in this format:
vehicle: "NUMBER", day: DAY, offence: "OFFENCE", penalty: PENALTY
The placeholders mean the following:
- NUMBER: the registration number of the law breaking vehicle
- DAY: the day of the offence, numbered like the timestamp parameter
- OFFENCE: the type of the offence, always one of
Outlawed entrance to CTRZ,Outlawed entrance to EORZ,Outlawed entrance to CTRZ & EORZ - PENALTY: the price that the driver is charged in this ticket
Print each photo attachment on a separate line, in the order specified before, in this format:
photo: PHOTO-ID, time: "TIME", road: "ROAD"
The placeholders mean the following:
- PHOTO-ID: the identifier of the attached photo, used by the real ticket renderer to print the photo
- TIME: the time of taking the photo in HH:mm:ss format, exactly the same as the timestamp
- ROAD: the name of the road on which the photo was taken
Follow the specified formats precisely, especially the order of parameters, the spacing, the punctuation and the quotation marks. Print a line containing ### between every two consecutive test cases.