# DWITE Online Computer Programming Contest

## Autocomplete

January 2010
Problem 4

Have you come across those online forms where you’d begin to type in a word, and it will give you suggestions as to how to end it? That’s autocomplete. It matches the beginning of the word against the dictionary of known (or relevant) words, and makes suggestions. Since the dictionary that I want you guys to have will be too big for an input file, you’d have to make your own.

1. Start with an array of 50,000 integers, from 0 to 49,999.
2. For each element, multiply it by the sum of its digits, then modulo by 99999.

It’s important that we are working with the same “words” here, so to check that you are doing this right, here’s an example: If the original seed is 12345, then the resulting word is (12345 × 15) % 99999 = 85176. Here are some extra checks, at various indexes of my dictionary:

• dictionary[0] = 0
• dictionary[9] = 81
• dictionary[10] = 10
• dictionary[12345] = 85176
• dictionary[49999] = 99979

The input file DATA4.txt will contain 5 lines, integers 0 ≤ N ≤ 49999, prefixes of words being entered.

The output file OUT4.txt will contain 5 integer results, the number of possible matches in the dictionary; that is, the number of words that have the input as a prefix (beginning with that sequence) or are that word in full.

Note 1: Words in the dictionary are not guaranteed to be unique. For example, 99990 appears in the dictionary 3 times. All 3 of them would count towards the answer.

Note 2: Be aware of the performance constraints. The judge will time out if you take too long.

Sample Input:
```10145
10144
10143
1008
9```
Sample Output:
```0
1
2
12
5349```