问题描述

呆子最近在研究计算生物学,一个问题困扰了呆子很久很久,于是他决定写成acm题目放在网上,
让大家帮帮忙!

计算生物学中,我们常常需要对两个或多个DNA序列进行比较,一个常用的办法是用得分矩阵的办法,比如下面
这个矩阵

score[4][4] = 

    A   G   C   T
A   7   5  10  10 
G   5   1 -10 -10 
C  10 -10   1 -10 
T  10 -10 -10   1 

设计矩阵的时候我们需要满足如下性质:(矩阵每个元素必须是整数)

   1。 矩阵对角元素 都 大于0
   2。 矩阵的任意元素 都在 -10 和 10 之间,包括 -10和10
   3。 矩阵是对称的
   4。 矩阵所有元素的和为0

有了上面这个矩阵,我们就可以比较两个长度相等的DNA序列了,比如对序列

AAA 和 AAC

他们两个比较的得分是:score(A,A) + score(A,A) + score(A,C) = 9 + 9 + 10 = 28。

呆子通过实验得到了n个长度相等的DNA串,如果有那么一个得分矩阵,那么呆子就可以算出
他们之间的平均比较得分了。平均比较得分是这样计算的,比如S(x,y) 是x和y两个串比较的得分,
那么平均比较得分就是

      S(串1,串2) + S(串1,串3) + ... + S(串1,串n) +
                   S(串2,串3) + ... + S(串1,串n) +
				...
				      S(串n-1,串n)

除以 n*(n-1) / 2。

可问题是呆子手里没有这样一个合适的得分矩阵,于是懒惰的呆子想啊,我的数据肯定是很好很好的,
合理的得分矩阵应该使得我的数据的平均比较得分尽可能的高才对!你能够帮呆子算出他的数据的
平均比较得分 最高可能是多少么?

输入描述

输入包含若干组输入数据,文件结束表示没有新的数据组了。

每组输入的第一行是一个整数n,表示呆子测得的 DNA 串的个数,( 1 < n <= 100 )
然后是n行输入,每行是一个DNA 序列,长度为L (0 < L <= 100),
每行的DNA序列保证一样长,而且只可能含有如下四个字母 A,G,C,T。

输出描述

对每组输入,输出一个表示最高可能的平均比较得分的值,保留两位小数。

输入样例

3
AAA
AAA
AAC
3
AAA
AAA
AAC

输出样例

30.00
30.00

From:  daizisheng