Optical Character Recognition
Time limit2sMemory limit1024 MB
Given n binary character samples and one binary image of the same size, print the 1-based index of the sample that matches the most cells.
- Level
Easy2 of 10
- Topics
- Array, Simulation
- Solved
- No attempts yet
Problem
The well-known company Maple is preparing to release its newest mobile phone, myPhone. Among other features, myPhone scans text with a built-in camera.
The phone must recognize different characters. A sample of a character is a rectangular table of cells. Each cell contains if ink should be present at that position of the character, and otherwise.
The scanning program splits the photographed image into rectangles of pixels (each pixel is either black, written as , or white, written as ) and compares them with the character samples.
To score a comparison, Maple's special department for Font Criteria by Finite Automata (КОШКА) defined the similarity of two tables. Similarity is the number of cells where the sample and the image have equal values.
Write a program that, given a set of characters and an image, finds the character most similar to the image by the КОШКА criterion, that is, the character with the greatest similarity.
Input
The first line contains three natural numbers , , and (). Then come blocks describing the character samples. Each block consists of lines of zeros and ones, with characters in each line. The image follows in the same format.
Output
Print one number, the index of the most similar character. Characters are numbered from 1 in the order they appear in the input. If several characters are tied, print any of them.