DWITE Online Computer Programming Contest, 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.

• Start with an array of ~50\,000~ integers, from ~0~ to ~49\,999~.
• For each element, multiply it by the sum of its digits, and take modulo ~99\,999~.
• This is your dictionary.

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 ~12\,345~, then the resulting word is ~(12\,345 \times 15) \mathbin{\%} 99\,999 = 85\,176~. Here are some extra checks, at various indices of my dictionary:

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

The input will contain 5 lines, integers ~0 \le N \le 49\,999~, prefixes of words being entered.

The output 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.

Note 1: words in the dictionary are not guaranteed to be unique. For example, ~99\,990~ 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

Problem Resource: DWITE