DWITE Online Computer Programming Contest
January 2010
Problem 4
Autocomplete

Have you came 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 a 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.

• Start with an array of 50,000 integers, from 0 to 49,000.
• For each element, multiply it by the sum of its digits, and take modulo 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, number of possible matches in the dictionary; that is number of words that have the input as a prefix (begin with that sequence) or are that word in full.

Note1: 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.

Note2: be aware of the performance constrains. The judge will time out if you take too long.

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