Time Zones
Time limit1sMemory limit128 MB
Given n messages with local hhmm timestamps arriving in chronological order for a hypothetical own-zone time, deduce each message's originating time zone under a westward-offset day-wraparound rule.
- Level
Medium6 of 10
- Topics
- Simulation, Math, Sorting
- Solved
- No attempts yet
Problem
You are a businessman with customers all over the world. During one day you receive exactly one message from each time zone, including the zone you are in. Every message carries the local time at which it was sent (messages are delivered instantly). Unfortunately, because of a bug, only the local time is given, with nothing to identify which time zone the message came from.
Your task is to determine which time zone each message originated from.
In this problem the number of hours in one day, n, is between 5 and 60. The number of time zones equals the number of hours, and each time zone has a time displacement that is a whole number of hours.
The zones are numbered 0 to n − 1. You live in and receive messages in zone 0, which has no displacement. The zones are counted westward, meaning that you add z hours to the local time in zone z to get the time in your zone. (Note that this is not the usual convention; normally zone 2 would be written as "-2:00".)
For example, if the local time in zone 2 is 03:15, then it is 05:15 in your zone.
Messages may arrive at any moment during the day (that is, between 0:00 and (n − 1):59), and no two messages arrive at the same time. The date line lies between zone 0 and the last zone, so it can be ignored.
Input
The first line contains the number of hours in one day, n (5 ≤ n ≤ 60), which is also the number of time zones and the number of messages you received.
Each of the next n lines contains one local sending time formatted as hhmm (two digits for the hours and two for the minutes, with 0 ≤ hh ≤ n − 1 and 0 ≤ mm ≤ 59). The lines are given in chronological order of arrival: the first message to arrive is on the first line.
It is guaranteed that the input has exactly one valid answer.
Output
Print a single line containing n integers between 0 and n − 1, giving the origin time zone of each message. The first integer corresponds to the first time in the input, and so on. Separate the integers with single spaces.
Hint
Consider the sample with n = 5. The message whose local time is 04:00 must come from zone 0; otherwise its arrival time would be later than 4:59, the last minute of a 5-hour day.