IOI '97 - Cape Town, South Africa

Character Recognition

This problem requires you to write a program that performs character recognition.

Each ideal character image has 20 lines of 20 digits. Each digit is a '0' or a '1'. See the sample input below for the layout of character images.

You are initially given representations of 27 ideal character images in this order:

_abcdefghijklmnopqrstuvwxyz

where _ represents the space character.

You are also given one or more potentially corrupted character images. A character image might be corrupted in these ways:

  • at most one line might be duplicated (and the duplicate immediately follows)
  • at most one line might be missing
  • some 0's might be changed to 1's
  • some 1's might be changed to 0's

No character image will have both a duplicated line and a missing line. No more than 30% of the 0's and 1's will be changed in any character image in the evaluation datasets.

In the case of a duplicated line, one or both of the resulting lines may have corruptions, and the corruptions may be different.

Write a program to recognize the sequence of one or more characters in the image provided in the input file using the font provided in file font.in.

Recognize a character image by choosing the font character images that require the smallest number of overall changed 1's and 0's to be corrupted to the given font image, given the most favourable assumptions about duplicated or omitted lines. Count corruptions in only the least corrupted line in the case of a duplicated line. You must determine the sequence of characters that most closely matches the input sequence (the one that requires the least number of corruptions). There is a unique best solution for each test case.

A correct solution will use precisely all of the data supplied in the input.

Input Format

  • The first 27×20 = 540 lines of input will contain the 27 ideal character images. Each character image spans 20 lines, and is 20 digits wide.
  • The next line contains an integer N (19 ≤ N < 1200).
  • The next N lines are each 20 digits wide, and contain the sequence of corrupted character images.
  • There are no spaces separating the zeros and ones in the data set.
                                         _
(digit1)(digit2)(digit3) ... (digit20)    \
(digit1)(digit2)(digit3) ... (digit20)     } 540 lines
...                                      _/
N                                        _
(digit1)(digit2)(digit3) ... (digit20)    \
(digit1)(digit2)(digit3) ... (digit20)     } N lines
...                                      _/

Output Format

Your program must output a single string of the characters recognized. Its format is a single line of ASCII text. The output should not contain any separator characters. If your program does not recognize a particular character, it must output a ? in the appropriate position.

Sample Input

An incomplete sample of a set of ideal character images. Only the image for a space and the letter 'a' is shown here. A corrupted sequence of character images for the string " a".
Line #DataLine #Data

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000111100100000000
00001111101110000000
00001101111110000000
00001100110110000000
00001100110110000000
00001110110110000000
00001111111110000000
00001111111110000000
00001111111100000000
00001100000000000000
00001100000000000000
00000000000000000000
00000000000000000000
00000000000000000000
...
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
39
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000111100100000000
00001111101110000000
00001101111110000000
00001100110110000000
00001100110110000000
00001110110110000000
00001111111110000000
00001111111110000000
00001111111100000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000

Sample Output

 a

Note that the output is a line with 2 characters: a space, followed by the letter 'a'.


Explanation

The image was corrupted in 2 of the 4 ways listed above:

  • First, the entire line containing the last two 1's for the letter 'a' was removed.
  • Then, the last two 1's of corrupted sequence were changed to 0's.

Scoring

Your score will be given as the percentage of characters correctly recognized. Your score will be 0 if your output does not have the same length as the correct answer, or if there is a wrong character instead of a '?'.

All Submissions
Best Solutions


Point Value: 30 (partial)
Time Limit: 2.00s
Memory Limit: 32M
Added: Dec 27, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Do I count a duplicated/missing line as 1 corruption?

I'm not sure I'm understanding your question; it seems to me that it's answered in the problem statement. Please go over it again carefully. If it doesn't answer your question, then please clarify.