RiseOJ – 소 유전체학

설명

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

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

Positions:    1 2 3 4 5 6 7 8

Spotty Cow 1: A A T C C C A T
Spotty Cow 2: A C 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부터 위치 5까지의 구간이 점박이 여부를 설명하기에 충분하다고 추측한다. 즉, 이 위치들(즉, 위치 $2 \ldots 5$ )의 문자들만 보고도 농부 존은 어떤 소가 점박이이고 어떤 소가 아닌지 예측할 수 있다. 예를 들어 이 위치들에서 GTCG라는 문자들이 보이면, 그 소는 반드시 점박이임을 알 수 있다.

점박이 여부를 설명할 수 있는 가장 짧은 위치 구간의 길이를 찾도록 FJ를 도와주자.

문제 출처: Brian Dean

제약

문제 출처: Brian Dean

입력 형식

입력의 첫째 줄에 $$N$$ ( $1 \leq N \leq 500$ )과 $$M$$ ( $3 \leq M \leq 500$ )이 주어진다. 다음 $$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
ACTTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

출력

문제 정보

riseoj 작성

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

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

태그

JudgeUSACO

소 유전체학

평가 및 의견

풀이 제출