Facebook Hacker Cup 2015 Round 1
Since you crave state-of-the-art technology, you've just purchased a phone with a great new feature: autocomplete!
Your phone's version of autocomplete has some pros and cons. On the one hand, it's very cautious. It only autocompletes a word when it knows exactly what you're trying to write. On the other hand, you have to teach it every word you want to use.
You have distinct words that you'd like to send in a text message in order. Before sending each word, you add it to your phone's dictionary. Then, you write the smallest non-empty prefix of the word necessary for your phone to autocomplete the word. This prefix must either be the whole word, or a prefix which is not a prefix of any other word yet in the dictionary.
What's the minimum number of letters you must type to send all words?
Input begins with an integer , the number of test cases. For each test case, there is first a line containing the integer . Then, lines follow, each containing a word to send in the order you wish to send them.
For the test case, print a line containing
Case #i: followed by the minimum number of characters you need to type in your text message.
The words will have a total length of no more than characters.
The words are made up of only lower-case alphabetic characters.
The words are pairwise distinct.
NOTE: The input file is about 10-20MB.
Explanation of Sample
In the first test case, you will write
hill, for a total of characters.
5 5 hi hello lol hills hill 5 a aa aaa aaaa aaaaa 5 aaaaa aaaa aaa aa a 6 to be or not two bee 3 having fun yet
Case #1: 11 Case #2: 15 Case #3: 11 Case #4: 9 Case #5: 3