wordRings

题目描述:

我们有n个（n<=100,000）字符串，每个字符串都是由a~z的小写英文字母组成的。如果字符串A的结尾两个字符刚好与字符串B的开头两个字符相匹配，那么我们称A与B能相连（注意：A能与B相连不代表B能与A相连）。我们希望从定的字符串中找出一些，使得它们首尾相接形成一个环串（一个串首尾相连也算），我们想要使这个环串的平均长度最长。如下例：

ababc

bckjaca

caahoynaab

第一串能与第二个串连，第二串能和第三个串相连，第三个串能和第一个串相连，我们按照此顺序相连，便形成了一个环串，长度为5+7+10=22（重复部分算两次），总共使用了3个串，所以平均长度是22/3约7.33.

输入格式:

多组数据

每组数据第一行一个整数n，表示字符串数量。

接下来n行每行一个长度小于等于1000的字符串。

读入以n=0结束

输出格式:

若不存在环串，输出”No solution“。否则输出最长的环串平均长度。误差在1e-6内算正确。

样例输入:

3
intercommunicational
alkylbenzenesulfonate
tetraiodophenolphthalein
0

样例输出:

21.66

时间限制: 1000ms
空间限制: 256MB

---