Digital Clock
Time Limit: 2 Seconds Memory Limit: 32768 KB
Electronic equipment commonly uses 7-segment elements to show numbers. A 7-segment element gets its name because it uses 7 line segments to show a shape: 3 horizontal segments and 4 vertical segments. Each segment can be independently switched on and off, making it possible to show any digit from 0 to 9.
To show more than 1 digit at the same time, a larger display is constructed by putting multiple 7-segment elements next to each other. In this case, each segment in each digit can be independently switched on and off. For example, electronic alarm clocks typically use four 7-segment elements to show the time of day: two digits for the hour (00 to 23) and two digits for the minutes (00 to 59).
You managed to find an old alarm clock in a dusty corner of the basement. Unfortunately, it does not seem to work very well: it does not always show the correct time. You suspect that this is due to faulty wires in the 7-segment display. As a result of the faults, some of the segments may not be working at all; they never light up, no matter which digits the clock tries to put on its display. On the other hand, the segments that do sometimes light up should all be working correctly. You thus assume that each of the 28 segments on the clock is either completely broken (never lights up) or is working perfectly fine (lights up precisely when it should).
You want to know what time it is, of course, but the silly clock is not making it very easy. You have been watching the clock for some time, writing down the pattern of digits on its display every minute. (Note that it is possible that the display stays the same for a few minutes. When that happens, you just write down the same pattern several times.) Your task is to find out what time the clock was really trying to show when you wrote down the first pattern of the sequence. The answer must be consistent with all observations of the clock display, for the first minute as well as for the following minutes, under the assumption that each display segment is either completely broken (never lights up) or is working perfectly.
There may be multiple possible answers. In that case, you should make a list of all possible answers, in order of increasing time of day. It is still possible that the clock is really broken in some other way than just faulty segments. In that case, it may happen that there is no possible answer which is consistent with all observations.
Input
For each test case, there is one line of input containing the following items:
• A positive integer N (1 ≤ N ≤ 50), the number of minutes you have been watching the clock.
• N items, each representing a pattern of digits that was observed on the clock. Each pattern is formatted as two decimal digits, followed by a ‘:’ character, followed by two more decimal digits.
The patterns are listed in the order in which they were seen on the clock.
It is theoretically possible for a faulty 7-segment display to show a shape which does not correspond to any of the digits from 0 to 9. However, for some mysterious reason, this never happened during the time you were watching the clock.
Output
For each test case, give one line of output.
If there is at least one possible answer, print a list of all possible answers separated by spaces.
Each possible answer must be a valid 24-hour clock time, formatted as two digits (00 to 23),
followed by a ‘:’ character, followed by two digits (00 to 59).
The list of possible answers must be printed in order of increasing time of day.
If there is no possible answer, print the word ‘none’.
Sample Input
1 88:88 2 23:25 23:26 3 71:57 71:57 71:07
Sample Output
none 23:25 00:58 03:58 07:58 08:58Submit
Source: NWERC 2012