실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 512 MB |
유전학자 세현은 마리의 반점이 있는 소와 마리의 반점이 없는 소를 소유하고 있다. 소 유전학 박사 과정을 밟은 그는, 소의 반점이 소 유전체의 한 위치에서 발생하는 돌연변이때문이라고 확신합니다.
큰 비용을 들여, 세현은 소들의 유전자를 분석한다. 각 유전자는 A, C, G, T의 네 개의 문자로 구성된 길이 의 문자열이다. 그가 소들의 유전자를 맞춰보면, 아래와 같은 표를 얻게 된다. 이는 인 경우를 보여준다.
위치: 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가 점박이를 설명할 수 있는 유전체의 잠재적 위치라는 것을 추측할 수 있다. 즉, 이 위치의 문자만을 살펴보면, 세현은 어떤 소가 반점이 있는 소이고 어떤 소가 아닌지를 예측할 수 있다(여기서, A 또는 G는 반점이 있는 소를, C는 반점이 없는 소를 의미한다; T는 세현의 소 중에서 위치 2에서 나타나지 않으므로 관련이 없다). 위치 1은 반점이 있는 소를 설명하는 데에 자체로는 충분하지 않다. 이 위치의 A는 반점이 있는 소 또는 반점이 없는 소를 나타낼 수 있기 때문이다.
세현의 소들의 유전자가 주어진다면, 반점이 있는 소일 가능성을 설명할 수 있는 위치의 수를 세어 보세요.
첫 번째 입력 줄에는 과 이 있고, 이들은 최대 100의 크기를 가진 양의 정수다. 다음 줄에는 각각 길이 의 문자열이 포함되어 있으며, 이들은 점박이 소들의 유전자를 설명한다. 마지막 줄은 반점이 없는 소들의 유전자를 설명한다.
유전자에서 반점이 있는 소를 설명할 수 있는 위치 수(범위는 의 정수)를 세어주세요. 위치는 만약 반점 특성이 세현의 소의 집단에서 완벽한 정확성으로 예측 될 수 있다면, 이 위치는 반점이 있는 소를 설명할 수 있는 잠재적인 위치입니다.
3 8 AATCCCAT GATTGCAA GGTCGCAA ACTCCCAG ACTCGCAT ACTTCCAT
1
출처: USACO 2017 US Open Contest, Bronze Problem 2. Bovine Genomics