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 G T T G C A ... T
Plain Cow 3:  A G T T C C A ... T

이 표를 자세히 살펴본 그는, 위치 2와 4만으로 점박이 여부를 설명하기에 충분하다고 추측한다. 즉, 이 두 위치의 문자들만 보고도 농부 존은 어떤 소가 점박이이고 어떤 소가 아닌지 예측할 수 있다(예를 들어 G와 C가 보이면 그 소는 반드시 점박이다).

농부 존은 점박이 여부가 한두 위치가 아니라 서로 다른 세 위치의 집합을 보아야 설명될 수 있다고 확신한다. 각각 점박이 여부를 설명할 수 있는, 서로 다른 세 위치로 이루어진 집합의 개수를 세도록 도와주자.

문제 출처: Brian Dean

제약

문제 출처: Brian Dean

입력 형식

입력의 첫째 줄에 $$N$$ ( $1 \leq N \leq 500$ )과 $$M$$ ( $3 \leq M \leq 50$ )이 주어진다. 다음 $$N$$ 개의 줄에는 $$M$$ 개의 문자로 이루어진 문자열이 하나씩 주어진다. 이는 점박이 소들의 유전체를 나타낸다. 마지막 $$N$$ 개의 줄은 점이 없는 소들의 유전체를 나타낸다.

출력 형식

점박이 여부를 설명할 수 있는, 서로 다른 세 위치로 이루어진 집합의 개수를 출력한다. 유전체에서 그 세 위치만 보고 농부 존의 소 집단에서 점박이 형질을 완벽한 정확도로 예측할 수 있다면, 그 세 위치의 집합은 점박이 여부를 설명한다.

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 > Silver

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

태그

JudgeUSACO

소 유전체학

평가 및 의견

풀이 제출