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, then modulo by 99999.
- 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 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.
10145
10144
10143
1008
9
0
1
2
12
5349