ZOJ Problem Set - 1748
The Olympic committee has hired American Code Masters (ACM) to verify the IDs issued to all the athletes, reserves, judges, staff, and the press. Each badge has a barcode written on it in base-5, encoding the ID number. The system of ID numbers uses a check-digit scheme to detect errors and reduce forgeries. You are to write a program to help ACM detect invalid ID numbers.
The devices that security uses to read the barcodes produce strings of the letters V,W,X,Y,Z. Each letter represents a base-5 digit: V represents 4, W represents 3, X represents 2, Y represents 1, and Z represents 0. So, WXZ=320 (base-5), which is 85 (base-10). The base-5 number is first converted to a base-10 number. Any number with more than 8 (base-10) digits is considered invalid. Numbers with less than 8 digits are padded on the left with zeroes. IDs are allocated based on the most significant digit (in base-10):
0, 1 athletes;
Consider the ID number d7 d6 ... d1 d0 expressed in base-10, where di (0 <= i <= 7) is a single digit of the ID number. For this ID to be valid the following checksum value must be 0:
F(0,d0) x F(1,d1) x F(2,d2) x ... x F(6,d6) x F(7,d7)
We will define the function F(i,j) and the operator next. The function F is defined as:
The definition of the function F depends on a permutation of the decimal digits we call G:
That is, G(0)=1, G(1)=5, etc.
The function i j is based on dihedral groups and has the nice property that transposing digits in the ID creates a checksum error. It is defined as follows:
Note that -4 mod 5 = 1.
The operator is left-associative, so for example i x j x k = (i x j) x k.
Source: Southeast USA 2000