Problem1082--「一本通 3.3 例 1」Word Rings

1082: 「一本通 3.3 例 1」Word Rings

Time Limit: 7 Sec  Memory Limit: 64 MB
Submit: 0  Solved: 0
Submit Status Web Board

Creator:

Description

原题来自:Centrual Europe 2005

我们有 nnn 个字符串,每个字符串都是由a至z的小写英文字母组成的。如果字符串 AAA 的结尾两个字符刚好与字符串 BBB 的开头两个字符匹配,那么我们称 AAABBB 能够相连(注意:AAA 能与 BBB 相连不代表 BBB 能与 AAA 相连)。我们希望从给定的字符串中找出一些,使得它们首尾相连形成一个环串(一个串首尾相连也算),我们想要使这个环串的平均长度最大。如下例:

ababc
bckjaca
caahoynaab

第一个串能与第二个串相连,第二个串能与第三个串相连,第三个串能与第一个串相连,我们按照此顺序相连,便形成了一个环串,长度为 5+7+10=225+7+10=225+7+10=22(重复部分算两次),总共使用了 333 个串,所以平均长度是 223≈7.33\frac{22}{3}\approx 7.333227.33


Input

本题有多组数据。

每组数据的第一行,一个整数 nnn,表示字符串数量;
接下来 nnn 行,每行一个长度小于等于 100010001000 的字符串。

读入以 000 结束。


Output

若不存在环串,输出No solution,否则输出最长的环串的平均长度。

只要答案与标准答案的差不超过 0.010.010.01,就视为答案正确。


Sample Input

3
intercommunicational
alkylbenzenesulfonate
tetraiodophenolphthalein
0

Sample Output

21.66

HINT

对于全部数据,1≤n≤1051\le n\le 10^51n105


Source/Category


Submit Status