WORDRING - Word Rings

题意翻译

### 题目描述 如果字符串A的**结尾两个**字符与字符串B的**开头两个**字符相匹配,我们称A与B能 **“ 相连 ”** ( 注意:A与B能相连,不代表B与A能相连 ) 当若干个串首尾 “ 相连 ” 成一个环时,我们称之为一个环串(一个串首尾相连也算) 我们希望从给定的全小写字符串中找出一个环串,使这个环串的平均长度最长 ``` intercommunicational alkylbenzenesulfonate tetraiodophenolphthalein ``` 如上例:第一个串能与第二个串相连,第二个串能与第三个串相连,第三个串又能与第一个串相连。按此顺序连接,便形成了一个环串。 长度为 20+21+24=65 ( **首尾重复部分需计算两次** ) ,总共使用了3个串,所以平均长度是 65/3≈21.6666 ### 输入格式 多组数据 每组数据第一行一个整数n,表示字符串数量 接下来n行每行一个长度**小于等于1000**的字符串 读入以n=0结束 ### 输出格式 若不存在环串,输出"No solution."。否则输出最长的环串平均长度。 Translated by @远藤沙椰

题目描述

A word ring is a sequence of words where the last two letters of each word are the same as the first two letters of the next word (and the last two letters of the last word are the same as the first two letters of the first word). For example, the following sequence is a word ring: ``` intercommunicational alkylbenzenesulfonate tetraiodophenolphthalein ``` Your task is to write a program that, given a list of words, finds a word ring. You have to make the word ring as impressive as possible: the average length of the words in the ring has to be as large as possible. In the above example, the average length is (20 + 21 + 24)/3 = 21.6666 , which makes it somewhat impressive. Note that each word can be used at most once in the ring, and the ring can consist of a single word.

输入输出格式

输入格式


The input contains several blocks of test cases. Each case begins with a line containing a single integer 1 <= n <= 100000 , the number of possible words that can be used. The next n lines contain these words. The words contain only the characters 'a'-'z' and the length of each word is at most 1000. The input is terminated by a block with n = 0.

输出格式


For each test case in the input, you have to output a single number on a separate line: the maximum average length of a ring composed from (a subset of) the words given in the input. The average length should be presented as a real number with two digits of precision. If it is not possible to compose a ring from these words, then output 'No solution.' (without quotes). To avoid rounding problems, we accept solutions with a maximum of 0.01(positive or negative) error.

输入输出样例

输入样例 #1

3
intercommunicational
alkylbenzenesulfonate
tetraiodophenolphthalein
0

输出样例 #1

21.66