Bar Code
Time limit1sMemory limit128 MB
Reconstruct the unique binary digit sequence from a partially unreadable bar code grid of black/white/unknown squares, or report it cannot be determined.
- Level
Medium6 of 10
- Topics
- Backtracking, String, Simulation
- Solved
- No attempts yet
Problem
To speed up the work of cashiers, each product is marked with a series of black and white vertical bars called a bar code. An optical reader can turn it into a sequence of zeros and ones that represents the product's code.
A bar code consists of black and white vertical bars, each of which can be thin or thick. White and black bars alternate; that is, no two adjacent bars have the same color. Regardless of its color, a thin bar represents 0 and a thick bar represents 1. Thus a bar code represents a sequence of binary digits.
Each bar is drawn as a column that is five 'squares' tall (see the picture below). A thin bar is one 'square' wide and a thick bar is two 'squares' wide. For example, the bar code shown below represents the sequence 010001.

The bar code reader used here was dropped on the floor, and since then it fails to recognize the color of some 'squares'.
Write a program that, given a scan produced by this faulty reader, determines which sequence of binary digits it represents, provided that sequence can be determined uniquely.
Input
The first line contains an integer N (1 ≤ N ≤ 100), the total width of the scanned bar code.
Each of the next five lines contains N characters. Each character is X, . (a dot), or ? (a question mark): X is a 'square' successfully recognized as black, . is a 'square' successfully recognized as white, and ? means the reader could not determine the color of that 'square'.
Output
Print a single line containing the sequence of binary digits represented by the bar code, if it can be determined uniquely. If the sequence cannot be determined uniquely, print the word UNDETERMINABLE instead.