开始 2023-01-11 14:00:00

USACO训练赛

结束 2023-01-11 15:20:00
Contest is over.
当前 2024-09-17 03:16:47

B. 【USACO】奶牛基因(USACO 2017 OPEN)

描述

Farmer John拥有N头带斑点的奶牛和N头不带斑点的奶牛。刚上完牛遗传学课程,他确信奶牛身上的斑点是 由牛基因组中单个基因的突变所引起的。
Farmer John花了大价钱来对他的奶牛们进行基因组测序。每个基因组都是一个长度为M的字符串,字符串仅由 A、C、G、T四种字符构成。当他列出奶牛的基因组时,他得到了如下一张表,在这里N = 3 :
位置: 1 2 3 4 5 6 7 ... M
斑点牛 1: A A T C C C A ... T
斑点牛 2: G A T T G C A ... A
斑点牛 3: G G T C G C A ... A
普通牛 1: A C T C C C A ... G
普通牛 2: A C T C G C A ... T
普通牛 3: A C T T C C A ... T
仔细地查看这张表,他推测位置2可能是潜在的突变基因。也就是说,只通过查看此位置的字符情况,Farmer John就能预测他的哪些奶牛有斑点,哪些没有斑点(在这里,a和g表示斑点,c表示普通;t无关紧要, 因为它不会出现在Farmer John的任意一头奶牛基因组的位置2上)。位置1本身不足以解释有无斑点,因为处 于该位置的a可能表示斑点牛或普通牛。
给定Farmer John的每头奶牛的基因组,请求出潜在的突变基因位置的数量。

输入

输入的第一行包括N、 M,两个正整数最多为100。接下来N行,每行为一个包含M个字符的字符串,表 示每头斑点牛的基因组。最后N行给出了每头普通牛的基因组。

输出

输出潜在的突变基因位置的数量(一个整数,在[0,M]之间)。一个位置是潜在的突变基因位置,当且仅当 Farmer John只通过查看每头奶牛在这个位置的字符,就能准确地预测出每头奶牛是否带有斑点。

样例

输入

3 8
AATCCCAT
GATTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

输出

1

Submit

登录

注册
时间限制 1 秒
内存限制 128 MB
提交