Skip to content

UKSPC 2002 Practice Problems » Tidbit Check Sum

Source
driver.c, driver.cpp, or driver.java
Input
standard input
Output
standard output

A check sum is used in various network protocols to insure that transmitted data is unaltered. For this problem, we will validate some data with a simple check sum. Our data will be a stream of digits of even length.

Our check sum works as follows. We first break our data up into tidbits. A tidbit is a number from 00 to 99, inclusive. As the data is being transmitted, each tidbit of data is added with the previous tidbit. As we add the numbers, we will store the sum in a two-digit tidbit-sum. Obviously one tidbit-sum cannot store the sum of a sequence of tidbits. So, we will ignore the carry as we add the numbers together. For example, if the sum so far was 99, and the next tidbit was 57, we would add the two tidbits and get 156. However, since we canít represent 156 in a tidbit-sum, we store the new sum as 56. After finishing the sum, we append a tidbit to the end of the data such that the sum of the new string of tidbits is zero. (The tidbit to append is equal to the value of 100 minus the tidbit-sum.)

Checking a string of tidbits that have had a checksum appended is easy. Simply add each tidbit, throwing out any carries generated by the addition, and see if the sum is zero. The program will check several tidbit strings for validity.

The input consists of one tidbit string per line. At the beginning of each line is an integer N between 0 and 1501 inclusive indicating the length of the tidbit sequence. This number is followed by N tidbits (numbers from 00 to 99). Every tidbit will consist of exactly two digits. Numbers will be separated by exactly one space. The end of input is signaled by a tidbit string with zero length (i.e. N = 0). The program will output whether each tidbit sequence is valid or invalid.

Sample Input Sample Output
1 00 valid
2 44 55 invalid
3 44 55 01 valid
6 22 33 44 55 66 77 invalid
7 23 34 45 55 66 78 99 valid
0