8．1 字串距离
【问题描述】
设有字符串 x，我们称在 x 的头尾及中间插入任意多个空格后构成的新字符串为 X 的扩展串，
如字符串 X 为“abcbcd”，则字符串“abcb□cd”，“□a□bcbcd□”和“abcb□cd□”都是 x 的扩展
串，这里“□”代表空格字符。
如果 A
1
是字符串 A 的扩展串，B
1
是字符串 B 的扩展串，A
1
与 B
1
具有相同的长度，那么我们定
义字符串 A
1
与 B
1
的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的
ASCII 码的差的绝对值，而空格字符与其他任意字符之间的距离为已知的定值 K，空格字符与空格
字符的距离为 0。在字符串 A、B 的所有扩展串中，必定存在两个等长的扩展串 A
1
、B
1
，使得 A
1
与
B
1
之间的距离达到最小，我们将这一距离定义为字符串 A、B 的距离。
请你写一个程序，求出字符串 A、B 的距离。
【输入】
输入文件第一行为字符串 A，第二行为字符串 B。A、B 均由小写字母组成且长度均不超过
2000。第三行为一个整数 K(1≤K≤100)，表示空格与其他字符的距离。
【输出】
输出文件仅一行包含一个整数，表示所求的字符串 A、B 的距离。
【样例】
blast.in
cmc
snmn
2
blast.out
1 0
8．2 血缘关系
【问题描述】
我们正在研究妖怪家族的血缘关系。每个妖怪都有相同数量的基因，但是不同的妖怪的基因可
能是不同的。我们希望知道任意给定的两个妖怪之间究竟有多少相同的基因。由于基因数量相当庞
大，直接检测是行不通的。但是，我们知道妖怪家族的家谱，所以我们可以根据家谱来估算两个妖
怪之间相同基因的数量。
妖怪之间的基因继承关系相当简单：如果妖怪 C 是妖怪 A 和 B 的孩子，则 C 的任意一个基因
只能是继承 A 或 B 的基因，继承 A 或 B 的概率各占 50％。所有基因可认为是相互独立的，每个基
因的继承关系不受别的基因影响。
现在，我们来定义两个妖怪 X 和 Y 的基因相似程度。例如，有一个家族，这个家族中有两个毫
无关系(没有相同基因)的妖怪 A 和 B，及它们的孩子 C 和 D。那么 C 和 D 相似程度是多少呢?因为 C
和 D 的基因都来自 A 和 B，从概率来说，各占 50％。所以，依概率计算 C 和 D 平均有 50％的相同
基因，C 和 D 的基因相似程度为 50％。需要注意的是，如果 A 和 B 之间存在相同基因的话，C 和 D
的基因相似程度就不再是 50％了。
你的任务是写一个程序，对于给定的家谱以及成对出现的妖怪，计算它们之间的基因相似程度。
【输入】
第一行两个整数 n 和 k。n(2≤n≤300)表示家族中成员数，它们分别用 1，2，…，n 来表示。k(0
≤k≤n-2)表示这个家族中有父母的妖怪数量(其他的妖怪没有父母，它们之间可以认为毫无关系，即
没有任何相同基因)。
接下来的 k 行，每行三个整数 a，b，c，表示妖怪 a 是妖怪 b 和 c 的孩子。
