
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 base5, encoding the ID number. The system of ID numbers uses a checkdigit 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 base5 digit: V represents 4, W represents 3, X represents 2, Y represents 1, and Z represents 0. So, WXZ=320 (base5), which is 85 (base10). The base5 number is first converted to a base10 number. Any number with more than 8 (base10) 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 base10): 0, 1 athletes; Consider the ID number d7 d6 ... d1 d0 expressed in base10, 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 leftassociative, so for example i x j x k = (i x j) x k.
Source: Southeast USA 2000 