Gallery Guards
Our university is opening two new galleries of modern art situated close to each other. To help guard the galleries in its first day of operation the management hired a number of student guards. The operating time of both galleries is from 08:00 to 17:59.Typically, a guard cannot spend the whole day in a gallery because of other duties. Therefore, each guard issues a set of time intervals in which he or she can guard a particular gallery.
The management needs to organize the guards effectively, they use concepts defined below.
Free time of a particular gallery is the total number of minutes in which no guard proposes to guard the gallery.
A proposed interval of a particular guard consists of a gallery name and also of the start and the end of a time interval which the guard is able to spend in the given gallery.
A guard cannot be present in both galleries simultaneously.
A conflict time of a guard is the total number of minutes he or she proposes to spend in both galleries simultaneously.
Time stamp is a string in format HH:MM, where HH represents hours and MM represents minutes. The numerical value of HH is always between 0 and 23, the numerical value of MM is always between 0 and 59. Both HH and MM contain exactly two digits. If necessary there are leading zeros in HH or MM or both. Time stamp always consists of 5 characters.
The task
You are given a list of guards and a list of their proposed intervals. For each gallery, compute its free time and for each guard compute their conflict time.
Input
The first input line contains two integers G and P, representing
the number of guards and the total number of proposed intervals.
The second line contains a list of all guard names.
The third line contains the names of the first gallery and the second gallery.
Next, P lines follow. Each line represents one proposed interval.
The line contains guard name, two time stamps and the gallery name.
The time stamps denote the start and the end of the guard's duty in the given gallery.
When the start and end time are equal it means the guard can spend in the
gallery exactly one minute denoted by the start (or end) time.
The proposed intervals are given in an arbitrary order. All items on all input lines are separated by comma followed by space.
It holds, 2 ≤ G ≤ 100, 2 ≤ P ≤ 1000.
Output
The first output line contains two time stamps separated by space. They represent the free time of the first and the second gallery (in their input order), respectively. Next, there are G lines containing a list of guards and their conflict times. Each line contains a time stamp of a guard conflict time followed by a space and the guard name. The list is sorted in ascending order of conflict times. The parts of list where guards share the same conflict time is sorted in ascending order of guard names.
Example 1
Input3, 6 Carlos, Emma Ann, Moira South hall, North hall Carlos, 09:00, 11:29, South hall Carlos, 10:00, 11:59, North hall Moira, 10:00, 16:59, North hall Emma Ann, 09:00, 09:59, North hall Emma Ann, 10:00, 11:59, South hall Moira, 10:00, 15:58, South hallOutput
03:01 02:00 00:00 Emma Ann 01:30 Carlos 05:59 Moira
Example 2
Input2, 8 A, B X, Y A, 12:15, 13:00, X A, 13:15, 14:00, X A, 12:45, 13:30, Y A, 13:45, 14:30, Y B, 14:15, 15:00, X B, 15:15, 16:00, X B, 14:45, 15:30, Y B, 15:45, 16:30, YOutput
06:56 06:56 00:48 A 00:48 B
Example 3
Input5, 10 Tom, Bob, Joe, Ela, Pet room1, room2 Tom, 10:00, 10:00, room1 Tom, 10:00, 10:00, room2 Bob, 11:00, 11:00, room1 Bob, 11:00, 11:01, room2 Pet, 12:00, 12:00, room1 Pet, 12:00, 12:02, room2 Ela, 13:00, 13:01, room1 Ela, 13:00, 13:03, room2 Joe, 14:59, 15:01, room1 Joe, 14:58, 15:03, room2Output
09:52 09:44 00:01 Bob 00:01 Pet 00:01 Tom 00:02 Ela 00:03 Joe
Public data
The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set