#172. 「一本通 3.3 例 1」Word Rings

「一本通 3.3 例 1」Word Rings

题目描述

原题来自:Centrual Europe 2005

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

ababc
bckjaca
caahoynaab

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

输入格式

本题有多组数据。

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

读入以 00 结束。

输出格式

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

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

样例

3
intercommunicational
alkylbenzenesulfonate
tetraiodophenolphthalein
0
21.66

数据范围与提示

对于全部数据,1n1051\le n\le 10^5