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 # | Data | Line # | 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)