In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of January 4th
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #12 exercise sheet]
After your journey to a distant planet in problem [AED071], you continued traveling through the same galaxy, discovering new planets. Quickly you found that all the planets in that galaxy used the same rules for words, except that the words were not limited to length 5.
Recall that the alien words are formed only by lowercase english letters: {a,b,c,…,z}. For a word to be considered valid, its letters must come in strictly ascending alphabetical order, that is, a letter can only appear after another letter if it also appears later in the alphabet.
For example, the following three words are valid: abc aep gwz
While the following three words are not: aab are cat
Each valid word is assigned an integer (the index) corresponding to its position in a list of all valid words ordered first by size and then alphabetically:
a -> 1 b -> 2 ... z -> 26 ab -> 27 ac -> 28 ... az -> 51 bc -> 52 ... vwxyz -> 83681 abcdef -> 83682 ... bcdefghijklmnopqrstuvwxyz -> 67108862 abcdefghijklmnopqrstuvwxyz -> 67108863
Given a list of N valid words, your task is to calculate the position (the indices) of each word.
The first line of input contains an integer N, indicating the number of words to consider. The following N lines each describe one valid word, with a length between 1 and 26 (inclusive).
The output should contain N lines. Each of these lines should indicate the word and the respective position (its index), as previously described.
The following limits are guaranteed in all the test cases that will be given to your program:
| 1 ≤ N ≤ 10 000 | Number of valid words |
| Example Input 1 | Example Output 1 |
4 ade a ac vwxyz |
ade 399 a 1 ac 28 vwxyz 83681 |
| Example Input 2 | Example Output 2 |
10 hpqx r isv wy gvwxyz vxyz kuxyz knuw jqsxyz hostxyz |
hpqx 14683 r 18 isv 2246 wy 347 gvwxyz 286779 vxyz 17900 kuxyz 80673 knuw 16303 jqsxyz 305742 hostxyz 939389 |