ZOJ Problem Set - 1523
Cheap small industrial scanners can only acquire images on gray scale, which are images where the pixels have intensity values in the integer range [0..255]. A company that builds automatic vending machines wants to use these small scanners to validate the tokens used in its machines. Tokens are small square chips of metal with holes strategically pierced. Tokens with different holes are used for different values.
A scanner will produce an image of the token introduced by the client and a
computer program will validate it. In the scanner image, metal appears as dark
pixels (values near 0) and holes appear as light pixels (values near 255). There
are two problems that must be solved in the validation process. The first problem
is that, since the token is square, a client can introduce it in the machine
slot in several possible ways. The second problem is due to the poor quality
of the image generated by those cheap scanners, which will contain 'noise' (errors).
To validate the token, the machine will compare the scanner output to a 'standard
image' of the token, previously produced using a high quality scanner.
For each test case your program should output a single line containing the confidence degree for the corresponding image. The confidence degree must be printed as a real number with two-digit precision, and the last decimal digit must be rounded. The input will not contain test cases where differences in rounding are significant.
Source: South America 2002