Clock Breaking
Time limit5sMemory limit512 MB
Given several consecutive LCD clock displays, find segments that are always burnt out, burnt in, working, or unknown across all consistent start times and fault assignments.
- Level
Hard9 of 10
- Topics
- Implementation, Brute force, Simulation
- Solved
- No attempts yet
Problem
ACME Clock Manufacturers has spent years answering complaints and lawsuits about faulty liquid-crystal display (LCD) screens. The executives finally decided to repair their quality control, and they hired you as a quality consultant. Your job is to write a program that tests a clock and finds the faults in its display.
Each of the four digits on one of these clocks uses a standard 7-segment LCD, and two extra small segments draw the colon ':'. The clock shows every time in a 24-hour format. The minute before midnight is 23:59 and midnight is 0:00. When the hour is below 10, the leading digit turns on no segment at all. On a clock with no faults, both colon segments are on at all times.
You are given what one clock displayed during several consecutive minutes, but you do not know the time at which those displays start. Some segments are burnt out, so they never turn on again, and some are burnt in, so they never turn off again. The rest work. Each segment is in one of these three states, and the state of one segment says nothing about the state of another.
Consider every start time and every assignment of segment states that explains the given displays. Decide which segments are faulty in all of them and which segments work in all of them.
The display is 7 rows by 21 columns. The four digits use columns 1 to 4, columns 6 to 9, columns 13 to 16, and columns 18 to 21, and the colon uses column 11 in rows 3 and 5. Here is the display with every segment on.
.XX...XX.....XX...XX.
X..X.X..X...X..X.X..X
X..X.X..X.X.X..X.X..X
.XX...XX.....XX...XX.
X..X.X..X.X.X..X.X..X
X..X.X..X...X..X.X..X
.XX...XX.....XX...XX.
The shapes of the digits 0 to 9 are below. The blank column between two shapes is there for readability.
.XX. .... .XX. .XX. .... .XX. .XX. .XX. .XX. .XX.
X..X ...X ...X ...X X..X X... X... ...X X..X X..X
X..X ...X ...X ...X X..X X... X... ...X X..X X..X
.... .... .XX. .XX. .XX. .XX. .XX. .... .XX. .XX.
X..X ...X X... ...X ...X ...X X..X ...X X..X ...X
X..X ...X X... ...X ...X ...X X..X ...X X..X ...X
.XX. .... .XX. .XX. .... .XX. .XX. .... .XX. .XX.

Figure 1: the LCD display of each digit.
Input
The first line contains one integer (), the number of consecutive minutes. The next lines contain displays of size , with one blank line between two neighboring displays.
Two characters draw each digit segment, and one character draws each colon segment. The character 'X' marks a segment that is on. The character '.' marks everything else, that is, a segment that is off or a position that belongs to no segment. No display puts an 'X' at a position that belongs to no segment, and no display shows only half of a two-character segment.
Output
Print one display of size . Print '0' for every segment that is burnt out, '1' for every segment that is burnt in, 'W' for every segment that is definitely working, and '?' for every segment whose state cannot be determined. Print '.' for every position that belongs to no segment. If the given displays cannot be those of consecutive minutes, print impossible instead.