DEPARTJ - Department

no tags 

The Department of Security has a new headquarters building. The building has several floors, and on each floor there are rooms numbered xxyy, where yy stands for the room number and xx for the floor number, 0 < xx, yy < 10.

The building has "paternoster" elevator, i. e. elevator build up from several cabins running all around. From time to time the agents must visit the headquarters. During their visit they want to visit several rooms and in each room they want to stay for some time. Due to the security reasons, there can be only one agent in the same room at the same time, The same rule applies to the elevators.

The visits are planned in the way ensuring they can be accomplished within one day. Each agent visits the headquarters at most once a day.

Each agent enters the building at the 1st floor, passes the reception and then starts to visit the rooms according to his/her list. Agents always visit the rooms by the increasing room numbers. The agents form a linear hierarchy according to which they have assigned their one letter personal codes. The agents with higher seniority have lexicographically smaller codes. No two agents have the same code.

If more then one agent want to enter a room, or an elevator, the agents have to form a queue. In each queue, they always stand according to their codes. The higher the seniority of the agent, the closer to the top of the queue he stands. Every 5 s (seconds) the first agent in the queue in front of the elevator enters the elevator. After visiting the last room in the headquarters each agent uses if necessary elevator to the first floor and exits the building.

The times necessary to move from a certain point in the headquarters to another are set as follows: Entering the building, i.e. passing the reception and reaching the elevator, or a room on the first floor takes 30 s. Exiting the building, i.e. stepping out of the elevator or a room on the first floor and passing the reception takes also 30 s. On the same floor, the transfer from the elevator to the room (or to the queue in front of the room), or from the room to the elevator (or to the queue in front of the elevator), or from one room to another (or to the queue in front of the room) takes 10 s. The transfer from one floor to the next floor above or below in an elevator takes 30 s. Write a program that determines time course of agent's visits in the headquarters.

Input

The input file contains the descriptions of n >= 0 visits of different agents. The first line of the description of each visit consists of agent's one character code C, C = A, ... Z, and the time when the agent enters the headquarters. The time is in the format HH:MM:SS (hours, minutes, seconds). The next lines (there will be at least one) contain the room number, and the length of time intended to stay in the room, time is in seconds. Each room is in a separate line. The list of rooms is sorted according to the increasing room number. The list of rooms ends by the line containing 0. The list of the descriptions of visits ends by the line containing the character dot.

Output

The output contains detailed records of each agent's visit in the headquarters. For each agent, there will be a block. Blocks are ordered in the order of increasing agent's codes. The first line of a block contains the code of agent. Next lines contain the starting and ending time (in format HH:MM:SS) and the descriptions of his/her activity. Time data will be separated by one blank character. Description will be separated from time by one blank character. Description will have a form Entry, Exit or Message. The Message can be one of the following: Waiting in elevator queue, Waiting in front of room RoomNumber, Transfer from room RoomNumber to room RoomNumber,Transfer from elevator to room RoomNumber, transfer from RoomNumber to elevator, Stay in room RoomNumber, Stay in elevator.

Print a blank line after each block.

Sample

Input
A 10:00:00
0101 100
0110 50
0202 90
0205 50
0
B 10:01:00
0105 100
0201 5
0205 200
0
.

Output
A
10:00:00 10:00:30 Entry
10:00:30 10:02:10 Stay in room 0101
10:02:10 10:02:20 Transfer from room 0101 to room 0110
10:02:20 10:03:10 Stay in room 0110
10:03:10 10:03:20 Transfer from room 0110 to elevator
10:03:20 10:03:50 Stay in elevator
10:03:50 10:04:00 Transfer from elevator to room 0202
10:04:00 10:05:30 Stay in room 0202
10:05:30 10:05:40 Transfer from room 0202 to room 0205
10:05:40 10:07:40 Waiting in front of room 0205
10:07:40 10:08:30 Stay in room 0205
10:08:30 10:08:40 Transfer from room 0205 to elevator
10:08:40 10:09:10 Stay in elevator
10:09:10 10:09:40 Exit

B
10:01:00 10:01:30 Entry
10:01:30 10:03:10 Stay in room 0105
10:03:10 10:03:20 Transfer from room 0105 to elevator
10:03:20 10:03:25 Waiting in elevator queue
10:03:25 10:03:55 Stay in elevator
10:03:55 10:04:05 Transfer from elevator to room 0201
10:04:05 10:04:10 Stay in room 0201
10:04:10 10:04:20 Transfer from room 0201 to room 0205
10:04:20 10:07:40 Stay in room 0205
10:07:40 10:07:50 Transfer from room 0205 to elevator
10:07:50 10:08:20 Stay in elevator
10:08:20 10:08:50 Exit

hide comments
msar: 2022-08-15 16:46:55

Thank you Alex Anderson.

Simes: 2019-09-11 22:07:23

Surprisingly tricky, even without having to reproduce the bugs. Kudos to @AlexAnderson for figuring it out. And a thumbs-down for having buggy output.

Last edit: 2019-09-12 12:55:49
AvmnuSng: 2014-02-06 20:37:41

@Alex : It's simply mentioned in the description that in case of two or more AGENTS are there for any particular task, form a queue and order is Z > Y > X .... > C > B > A

Alex Anderson: 2013-02-01 18:54:58

Also, my Java code is about 500 lines, and the C code that was the incorrect judge solution was over 425.

Alex Anderson: 2012-11-04 05:55:52

Some notes if anyone wants to get AC on this problem:

1. The elevator situation means that every 5s (so ::00, ::05, ::10, etc) there is a completely 100% new elevator available on every single floor. These elevators are never reused once an agent gets off of it. Only one elevator is available per floor at those times.

2. 0 < xx, yy <= 10 [ not < 10]

3. Arbitrarily, if you are going to get on an elevator from floor 10 to go back down to floor 1 and leave, subtract 4:30, instead of adding it like normal.
ex: 11:04:30 11:00:00 Stay in elevator
not 11:04:30 11:09:00 Stay in elevator
(Note: it might be any amount of going down causes the bug, but I did this and was fine)

4. Arbitrarily, for the particular message "Transfer from elevator to room xxyy" use the misspelling 'ro' instead of 'to'

Clearly back in the day the judges didn't bother to even verify that their solution matched the sample test case that they gave.

Problem source: 1995 Central European Regionals

Last edit: 2012-11-08 04:56:29
Alex Anderson: 2012-11-04 05:36:29

More comments: So, I've found a solution that gets AC. I'm checking the results against the only judge test case I've found, and they are clearly wrong. The final output after taking the elevator from the 10th floor down to the 1st subtracts time instead of adds time, which is clearly wrong, and it does this for several agents.

EDIT: Yep, I changed 2 things to get "accepted" - If I am getting onto an elevator on the 10th floor only, I subtract time instead of adding it. ALSO when I use the phrase "Transfer from elevator to room xxyy", instead use the misspelling "ro"

Last edit: 2012-11-04 05:45:21
Alex Anderson: 2014-02-06 19:54:21

Problem statement is a massive mix of un-clarity and missing information.

The description of how the elevators work is unclear. Attempting to look up judge solutions, some judges consider "Every 5 s" to mean that elevators are only available at the 5s marks of time, whereas others take it to mean "after an elevator is used, the next is available in 5s". Further more, this issue is compounded since it doesn't explain that there are "sort of enough" elevators everywhere.

Next, all judge solutions or attempted solutions that I could find were obviously wrong.

Lastly, I submitted on poj.org, got AC, but submitted on UVA and got WA. poj.org does not have the below mistake, while the problem statement on UVA does.

Also note that the input description is addtionally wrong in specifying that xx,yy < 10. It is that xx, yy <= 10. I'm completely uncertain how such a mistake was made in the first place, when copy paste should be used.

Last edit: 2012-11-04 05:26:29
Alex Anderson: 2014-02-06 20:28:01

Another question:
Suppose a room is currently in use, and Agent B is waiting to use the room. At the exact time that the room becomes free, Agent A also arrives at the room.

Does B get into the room, or does A?

Alex Anderson: 2014-02-06 20:30:01

The output description is slightly unclear with regards to one part that I can find so far - Suppose we use the elevator to go from floor 1 to floor 8.

Do we output the message "Stay in elevator" 7 times, or only once? I'll test it eventually, maybe.

Also, I'm not sure I understand the elevator situation. Are there just "enough" elevators such that no matter where someone is waiting, there will be an available elevator just for them within 5s?

Does time go from 00:00:00 to 23:59:59?

Last edit: 2012-11-03 15:54:51
Goffredo Baroncelli: 2012-03-13 17:33:43

I am trying to solve this problem. My code is able to reproduce the sample output, however fail with "wrong answer" when I submit it. Does anyone is able to share ideas how check my program ?


Added by:Andres Tellez
Date:2011-09-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64