Not an official ACM page
[Problem F | 1995 East-Central problem set | My ACM problem archive | my home page]

1995 East-Central Regionals
ACM International Collegiate programming Contest

sponsored by Microsoft

Problem E - LED Test

Many electronic devices have digital read-outs that are made using light-emitting diode (LED) arrays. A common digital display element uses seven, bar-shaped LED's, with the seven LED bars (segments) arranged and identified as: Manyelectronic devices have digital read-outs that are made using light-emitting diode (LED) arrays. A common digital display element uses seven, bar-shaped LED's, with the sevenLED bars (segments) arranged and identified as:

Seven Segments Configuration
Digits are displayed by illuminating various combinations of the seven segments in accordance with the following table: 
  Digit     Segments Illuminated (Y-Yes, N-No) 
Displayed   a  b  c  d  e  f  g 

    0       Y  Y  Y  Y  Y  Y  N 
    1       N  Y  Y  N  N  N  N 
    2       Y  Y  N  Y  Y  N  Y 
    3       Y  Y  Y  Y  N  N  Y 
    4       N  Y  Y  N  N  Y  Y 
    5       Y  N  Y  Y  N  Y  Y 
    6       Y  N  Y  Y  Y  Y  Y 
    7       Y  Y  Y  N  N  N  N 
    8       Y  Y  Y  Y  Y  Y  Y 
    9       Y  Y  Y  Y  N  Y  Y
For example, the digit three (3) would be displayed as the illumination of the segments {a,b,c,d,g} as:

The problem below is abstracted from one occurring in the incoming-parts inspection department, in a microwave-oven manufacturing facility. The incoming seven-segment LED's are checked for their proper functioning by automated equipment running under programmable control. Note: The solution to the problem below will not be a complete nor necessarily useful test for the actual inspections that would be conducted.

You are to create a program that will observe successive sets of illumination conditions of the seven segments of a single-digit display, and decide whether the sequence of illuminations could have been a valid "count down" sequence.

Unfortunately, for the LED your program is to observe, some of the segments may be burned out at the start of your test, and additional segments may burn out during the test. No segments will ever fail into the ON mode; no burned out segments will recover. Nevertheless, you are expected to be able to "read" through the ambiguities this malfunctioning display presents, by watching the display count down through one or more values.

Input

The input consists of a series of data sets having the following format:
First line -- A single unsigned integer,N,with value greater than zero (0) and less than eleven(11). The integer is left-justified on the input line.

Next N lines -- Each line has a string of seven(7) contiguous Y/N characters showing the light condition of the segments of the LED display. These successive lines supposedly represent a "count down" sequence. The first of these seven characters, the illumination reading for the "a" segment, will be the first character on a line.

The end of data is signaled by a null data set having a zero on the first line and no further data.

There is no information about where the "count down" sequence begins for a given data set. There is no information that carries over from one data set to the next; each data set represents a different LED being tested.

Output

For each supposed "count down" sequence you receive as a data set, you are to reply either:
MATCH
-or-
MISMATCH
depending on whether this sequence could possibly be a valid "count down" sequence somewhere within the sequence { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 } if an unknown number of burned-out segments were present at the beginning of the test, and, with possible burn-outs occurring during the test. Your output must be at the beginning of the line.

Sample Input

1
YYYYNYY
2
NNNNNNN
NNNNNNN
2
YYYYYYY
YYYYYYY
3
YNYYYYY
YNYYNYY
NYYNNYY
3
YNYYYYN
YNYYNYN
NYYNNYN
3
YNYYYYN
YNYYNYN
NYYNYYN
4
YYYYYYY
NYYNNNN
NNYYYYN
NNNYNNN
3
NNNNNNN
YNNNNNN
NNNNYNN
0

Output for the Sample Input

MATCH
MATCH
MISMATCH
MATCH
MATCH
MISMATCH
MATCH
MATCH

Judge's Data

This page maintained by Ed Karrels.
Last updated November 6, 1997