Chain of Words
All submissions for this problem are available.
Chef has invented a brand new dish in his restaurant. He decided to name it in an interesting way. Chef is a big fan of “Chain of Words”. Chain of words is a chain which is made up of words arranged in such a way that the last letter of each word is equal to first letter of the word connected to it. For example,
abc->cbd->def is a valid word chain of length 3. Now chef wants to use this method to name his new dish. He will choose some or all of the words present in his dictionary to form a chain in such a way that maximum words are used from his dictionary. If there are multiple chains possible with same length then choose the one which comes alphabetically first. Now each word of this word chain is concatenated so as to form a single word. Above described chain can be written as, abccbddef. This is the name of recipe. Chef wants to know the length of the name of recipe thus formed.
First line of input contains a number T<=100, number of test cases. Each test case consists of two lines, first line contains a number N<=60, the number of words in his dictionary. Next line contains N space separated words of length <= 30.
For each test case print the length of the name of recipe thus formed.
Input: 1 4 abc def cbd ghi
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.