MIB - Spelling Lists
J, of the Men In Black, has been learning an alien language and has has a spelling test tomorrow. J, however, is bored of studying the nonsensical (and often unpronouncable) words.
Instead, he is seeing how many ways he can reorder his spelling list. After making all possible permutations of word on his list, he sorts the rearranged lists lexiographically (by the first word, then the second...). After the sort, in what position, with the lexiographically first list being in position 1, is his original spelling list?
Input
The first line is the number of spelling lists (no more than 10).
For each spelling list, a line with the number of words (no more than 1000) is given, followed by the original list on the next line.
All words within a spelling list are unique. Each word is composed of the letters a-z, is fewer than 100 characters, and is followed by a single space.
Output
On separate lines, give the positions of the original lists.
Example
Input:
4
4
a b c d
4
d c b a
1
mrsmith
6
a aaaaaa aaaaa aaaa b bb
Output:
1
24
1
55
hide comments
lowgradde:
2024-11-05 11:25:31
You can map the input to lexicographical indices and then use recursion. |
|
antonkal:
2024-07-31 20:30:24
Naive solution:
|
|
cypher70:
2023-02-15 07:51:10
Use a big integer or any similar library because the answer will not fit in long datatype. |
|
Vijai Shankar Natarajan:
2009-06-14 12:19:44
After the sort, in what position, with the lexiographically first list being in position 1, is his original spelling list?
|
|
Paul Draper:
2009-06-01 16:16:03
I apologize. I have added an upper limit on the number of characters.
|
|
lost:
2009-06-01 16:15:22
what is the maximum number of characters in a single word? Also please check whether the input file is according to the input specification or not. I am getting runtime error on using gets function, while using scanf results in TLE. |
Added by: | Paul Draper |
Date: | 2009-05-28 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |