This page is still under construction.

Parts of this page are still being built. What you see may change.

Intelligent Traffic Surveillance

Time limit1sMemory limit128 MB

Summary
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 (00≤HH≤2300 \le HH \le 23, 00≤mm,ss≤5900 \le mm, ss \le 59).

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 NN, the total number of lines in the log files (1≤N≤10001 \le N \le 1000). The second line contains a string WW followed by two positive integers CTPCTP and EOPEOP. String WW is one of the words Saturday, Sunday, Monday, Tuesday, Wednesday, Thursday, or Friday, specifying the weekday of the deployment day, day 0. Numbers CTPCTP and EOPEOP are the penalty values for an outlawed entrance to CTRZ and to EORZ respectively, with EOP<CTPEOP < CTP. Each of the next NN 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 10910^9. 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.

Examples1

  1. Example 1

    Input
    6
    Friday 30000 25000
    setRoadZone 1 "09:12:53" "CTRZ" "Enghelab" "Ferdowsi" "Behesht"
    setRoadZone 1 "14:32:01" "EORZ" "Resalat" "Damavand"
    addZoneException 1 "09:00:13" "1000100" "1000200" "1000300"
    addPhotoInfo 2 "13:18:43" 1004 "Enghelab" "1000100" "1000200" "1000400" "1000105"
    addPhotoInfo 3 "11:55:12" 1003 "Behesht" "1000400" "1000105"
    addPhotoInfo 2 "06:30:00" 1002 "Resalat" "1000100" "1000105" "1000120" "1000400"
    3
    Sunday 100 90
    setRoadZone 4 "01:02:03" "CTRZ" "16-e_Azar"
    addPhotoInfo 4 "10:15:13" 211 "16-e_Azar" "1010101"
    addPhotoInfo 5 "20:21:42" 212 "16-e_Azar" "2020202"
    6
    Monday 1000 900
    setRoadZone 13 "09:00:00" "CTRZ" "Azadi"
    addPhotoInfo 13 "10:00:00" 101 "Azadi" "1000001"
    addPhotoInfo 14 "10:00:00" 102 "Azadi" "1000001"
    setRoadZone 15 "09:00:00" "UZ" "Azadi"
    addPhotoInfo 15 "10:00:00" 103 "Azadi" "1000001"
    addPhotoInfo 16 "10:00:00" 104 "Azadi" "1000001"
    0
    
    Expected output
    vehicle: "1000105", day: 2, offence: "Outlawed entrance to CTRZ", penalty: 30000
    photo: 1004, time: "13:18:43", road: "Enghelab"
    vehicle: "1000105", day: 3, offence: "Outlawed entrance to CTRZ", penalty: 30000
    photo: 1003, time: "11:55:12", road: "Behesht"
    vehicle: "1000120", day: 2, offence: "Outlawed entrance to EORZ", penalty: 25000
    photo: 1002, time: "06:30:00", road: "Resalat"
    vehicle: "1000400", day: 2, offence: "Outlawed entrance to CTRZ & EORZ", penalty: 30000
    photo: 1002, time: "06:30:00", road: "Resalat"
    photo: 1004, time: "13:18:43", road: "Enghelab"
    vehicle: "1000400", day: 3, offence: "Outlawed entrance to CTRZ", penalty: 30000
    photo: 1003, time: "11:55:12", road: "Behesht"
    ###
    ###
    vehicle: "1000001", day: 14, offence: "Outlawed entrance to CTRZ", penalty: 1000
    photo: 102, time: "10:00:00", road: "Azadi"
    vehicle: "1000001", day: 15, offence: "Outlawed entrance to CTRZ", penalty: 1000
    photo: 103, time: "10:00:00", road: "Azadi"