3499번 - 미토콘드리아 이브 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 91 | 29 | 26 | 30.952% |
문제
미토콘드리아 DNA는 생물의 세포 내에 있는 미토콘드리아의 DNA 분자이다.
이 DNA는 모계로부터 유전된다. 즉, 전 인류의 공통 모계 조상인 "미토콘드리아 이브"가 존재한다. 모계 조상은 가계도의 여성 부분을 타고 거슬러 올라가면 나오는 조상이다. 예를 들어, 어머니나 할머니가 자식의 모계 조상이 된다.
인류의 미토콘드리아 이브는 약 20만년 전 동아프리카에 살았던 것으로 추정된다.
이 문제에서는 이형 접합인 진핵 생물 단일종으로 이루어진 한 집단에 대해 다룬다. 연구자들은 이 집단의 개체 수 성장을 시간을 두고 완벽하게 기록했고, 그 중 몇 개체들의 미토콘드리아 DNA를 서열화했다. 관찰한 집단의 미토콘드리아 DNA는 모계로부터 유전될 때 돌연변이 없이 유전되었다고 가정한다.
현재 살아있는 모든 개체가 같은 미토콘드리아 DNA를 가졌는지 확인하는 프로그램을 작성하시오.
입력
입력의 첫 줄에 관찰을 시작한 시기에 살아있던 개체의 수인 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 이 개체들의 ID는 1부터 n까지 정수이다.
다음 n 줄에는 각 줄마다 하나의 문자가 주어진다. i 번째 줄의 문자는 ID가 i인 개체의 성별을 의미하는데, M은 수컷, F는 암컷을 의미한다.
다음 줄에는 관측 기간 동안의 출생과 사망한 횟수의 합인 정수 m (0 ≤ m ≤ 100,000)이 주어진다.
다음 m 줄에는 출생과 사망에 대한 정보가 시간순으로 주어진다.
출생은 세 단어로 주어지는데, 순서대로 아빠의 ID, 엄마의 ID, 성별을 나타낸다. (위와 마찬가지로 M은 수컷, F는 암컷이다) 새끼의 ID는 그때까지 ID로 쓰이지 않은 가장 작은 양의 정수이다.
사망은 음수 하나로 주어지는데, 죽은 개체의 ID에 마이너스 부호를 붙인 것이다.
그 다음 줄에는 서열화된 미토콘드리아 DNA의 수인 정수 k(0 ≤ k ≤ n + m)가 주어진다.
다음 k 줄에서, 각 줄에서 공백으로 구별되는 두 정수가 주어지는데, 전자는 미토콘드리아 DNA가 분석된 개체의 ID이고, 후자는 그 개체의 미토콘드리아 DNA의 고유 식별 번호이다. 두 미토콘드리아 DNA의 고유 식별 번호가 같을 때는 두 DNA가 같을 경우 밖에 없다. 미토콘드리아 DNA의 고유 식별 번호는 1부터 109까지의 정수이다.
입력의 모든 주어진 데이터는 모순이 없고, 한 개체의 미토콘드리아 DNA는 최대 한 번만 분석된다. 관찰이 끝났을 때 최소 하나의 개체는 살아 있다.
출력
출력은 하나의 단어이다.
- YES - 실험이 끝났을 때 생존한 개체가 모두 같은 미토콘드리아 DNA를 가지는 경우.
- NO - 실험이 끝났을 때 생존한 어떤 개체들이 서로 다른 미토콘드리아 DNA를 가지는 경우.
- POSSIBLY - YES와 NO를 확정할 수 없는 경우.
예제 입력 1
4 M F M F 12 3 4 F 1 2 M 1 2 M 3 4 F -3 -2 -4 -1 6 5 M 7 5 F -7 -6 0
예제 출력 1
YES
예제 입력 2
3 F F M 3 3 2 M 3 1 F -3 2 4 100500 5 100500
예제 출력 2
YES
예제 입력 3
3 M F M 2 1 2 M 3 2 F 0
예제 출력 3
POSSIBLY
예제 입력 4
2 M F 2 1 2 M -2 2 1 2011 2 2012
예제 출력 4
NO
출처
ICPC > Regionals > Northern Eurasia > Northern Eurasia Finals > NEERC 2011 E번
- 문제를 번역한 사람: wwiiiii
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호