DNA Sequencing

프로그램 명: usa_dna

제한시간: 1 초

농부 존은 그의 가축들의 족보를 공부하고있다. 그는 M(1<=M<=20)마리의 숫소와 F(1<=F<=20)마리의 암소를 갖고 있다. 그도 어떤 송아지가 다른 어떤 소의 새끼인지 모릅니다.

농부 존은 그의 농장에 있는 숫소와 암소 각각의 연속된 DNA_i 를 알고 있습니다. DNA_i는 오직 대문자 'A','C','G' 그리고 'T'로만 이루어진 25길이의 문자열을 가지고 있습니다. 그는 어떤 송아지가 어떤 암소와 숫소 한쌍의 새끼가 될 수 있는 가능성을 결정하고 싶어합니다.

농부 존이 결정을 내릴 수 있도록 도와주세요. 각각의 암소 한마리와 숫소 한마리의 한쌍에서 얼마나 많은 존의 송아지들이 소 한쌍의 새끼일 가능성이 있는지 출력해주세요.

송아지가 입력된 암소와 황소의 새끼가 될 수 있는 경우 :

그것들은 그것들의 부모가 될 수 없습니다(즉, 입력된 소가 자신의 어미가 될 수 없고 아비가 될 수 없습니다.)
송아지의 연속된 DNA와 부모의 각각의 연속된 DNA는 적어도 한개의 문자가 같은 위치에 있어야합니다.

예를들어 'ABC'는 ('axx','xbc')쌍에서는 나올 수 있지만 ('aaa','bbb')쌍에서는 나올 수 없습니다.

3마리의 숫소와 2마리의 암소의 연속된 DNA를 고려해봅시다. :

       Bull 1: GTTTTTTTTTTTTTTTTTTTTTTTT 
       Bull 2: AATTTTTTTTTTTTTTTTTTTTTTT 
       Bull 3: GATTTTTTTTTTTTTTTTTTTTTTT 
       Cow 1:  TTTTTTTTTTTTTTTTTTTTTTTTT 
       Cow 2:  ATTTTTTTTTTTTTTTTTTTTTTTT

Bull 2와 cow 1은 cow 2의 부모가 될 수 있습니다 :

       Bull 2: AATTTTTTTTTTTTTTTTTTTTTTT 
       Cow 1:  TTTTTTTTTTTTTTTTTTTTTTTTT 
       Cow 2:  ATTTTTTTTTTTTTTTTTTTTTTTT

cow 2의 첫번째 문자 'A'는 Bull 2에서 가져왔고, cow 2의 두번째 문자 'T'는 cow 1에서 가져왔고, 나머지 문자들은 부모 둘 중 아무나한테서 올 수 있습니다.

당신은 숫소와 암소의 DNA 배열에서 나올 수 있는 새끼의 수를 행렬로 만들어야 합니다.

입력

첫번째 줄 : 정수 M과 F의 입력.
두번째 줄 부터 M+i번째 줄 : i+1번째 줄에 숫소 i의 연속된 DNA_i를 입력.
M+2번째 줄에서 M+F+1번째 줄 : j+M+1번째 줄에 암소 j의 연속된 DNA_j입력.

출력

첫번째 줄 부터 M번째 줄 : i 번째 줄 : 공백으로 구분된 정수 F. j번째 정수는 i번째 숫소와 j번째 암소 사이에서 나올 수 있는 송아지의 수이다.

입출력 세부 정보

입력 세부 정보 : 
두마리의 숫소 DNA 다음에 세마리의 암소 DNA. 

출력 세부 정보 : 
bull 1과 cow 1을 생각해보자 : 
    b1: TGAAAAAAAAAAAAAAAAAAAAAAA 
    c1: ATAAAAAAAAAAAAAAAAAAAAAAA 

그들의 DNA의 중요한 부분인 {T|A} 와 {G|T} 하나의 가능성을 표현 할 수 있다. 

bull 0과 cow 0의 짝짓기 결과 : 

    b1: TGAAAAAAAAAAAAAAAAAAAAAAA -- 부모, 새끼가 될 수 없다. 
    b2: AGAAAAAAAAAAAAAAAAAAAAAAA 새끼! [TA][GT]와 연결된다. 
    c1: ATAAAAAAAAAAAAAAAAAAAAAAA -- 부모, 새끼가 될 수 없다. 
    c2: AAAAAAAAAAAAAAAAAAAAAAAAA -- 두번째 문자가 'A'이다; 반드시 'G'또는 'T'여야 한다. 
    c3: TTAAAAAAAAAAAAAAAAAAAAAAA 새끼! [TA][GT]와 연결된다. 

따라서. 배열의 첫번째 요소는 2입니다. 다른 요소들도 유사한 방법으로 나옵니다. 

역시 오역 의역 존재합니다. 

근데 마지막에 bull 0과 cow 0이 좀 헷갈릴거 같은데 배열의 [0,0]번째라고 생각하시면됩니다.

※ 참고
숫소 3마리와 암소 2마리에서 나올 수 있는 행렬은 3x2 행렬
숫소 2마리와 암소 3마리에서 나올 수 있는 행렬은 2X3 행렬

출처:usaco
번역:iam6ear

[질/답] [제출 현황] [푼 후(0)]

[ 채 점 ] [홈으로] [뒤 로]