RiseOJ – 소 유전체학

설명

농부 존은 점박이 소 $$N$$ 마리와 점이 없는 소 $$N$$ 마리를 기르고 있다. 소 유전학 강의를 막 수료한 그는, 소의 점이 소 유전체의 단 한 위치에서 일어난 돌연변이 때문에 생긴다고 확신한다.

농부 존은 큰 비용을 들여 소들의 유전체를 시퀀싱한다. 각 유전체는 A, C, G, T 네 문자로 이루어진 길이 $$M$$ 의 문자열이다. 소들의 유전체를 나란히 정렬하면 다음과 같은 표를 얻는데, 여기서는 $$N=3$$ 인 경우를 보였다.

Positions:    1 2 3 4 5 6 7 ... M

Spotty Cow 1: A A T C C C A ... T
Spotty Cow 2: G A T T G C A ... A
Spotty Cow 3: G G T C G C A ... A

Plain Cow 1:  A C T C C C A ... G
Plain Cow 2:  A C T C G C A ... T
Plain Cow 3:  A C T T C C A ... T

이 표를 자세히 살펴본 그는, 위치 2가 점박이 여부를 설명할 수 있는 유전체상의 잠재적 위치라고 추측한다. 즉, 이 위치의 문자만 보고도 농부 존은 어떤 소가 점박이이고 어떤 소가 아닌지 예측할 수 있다(여기서는 A 또는 G면 점박이, C면 점이 없다. T는 위치 2에서 농부 존의 어느 소에도 나타나지 않으므로 무관하다). 위치 1은 이 위치의 A가 점박이 소를 나타낼 수도, 점이 없는 소를 나타낼 수도 있으므로, 그 자체만으로는 점박이 여부를 설명하기에 충분하지 않다.

농부 존의 소들의 유전체가 주어질 때, 그 자체만으로 점박이 여부를 잠재적으로 설명할 수 있는 위치의 개수를 세시오.

문제 출처: Brian Dean

제약

문제 출처: Brian Dean

입력 형식

입력의 첫째 줄에 $$N$$ 과 $$M$$ 이 주어지며, 둘 다 100 이하의 양의 정수이다. 다음 $$N$$ 개의 줄에는 $$M$$ 개의 문자로 이루어진 문자열이 하나씩 주어진다. 이는 점박이 소들의 유전체를 나타낸다. 마지막 $$N$$ 개의 줄은 점이 없는 소들의 유전체를 나타낸다.

출력 형식

점박이 여부를 잠재적으로 설명할 수 있는 유전체상 위치의 개수( $0 \ldots M$ 범위의 정수)를 출력한다. 유전체에서 그 위치 하나만 보고 농부 존의 소 집단에서 점박이 형질을 완벽한 정확도로 예측할 수 있다면, 그 위치는 점박이 여부를 잠재적으로 설명한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 cownomics.in · 출력을 쓸 파일 cownomics.out

예제 1

입력

3 8
AATCCCAT
GATTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > US Open > Bronze

올림피아드 > USACO > 2016-2017 > US Open > Bronze

태그

JudgeUSACO

소 유전체학

평가 및 의견

풀이 제출