2265번 - 거짓말쟁이 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 78 | 13 | 5 | 38.462% |
문제
로빈슨 크루소가 탄 배는 폭풍우에 난파되었고, 그는 우여곡절 끝에 혼자서 한 섬에 도착하게 되었다. 그는 지치고 절망하였지만 불행 중 다행으로 어릴 때 들은 도착한 섬에 대한 전설을 아직도 생생히 기억할 수 있었다. 그 전설에 따르면 섬에는 선한 사람으로 구성된 종족과 악한 사람으로 구성된 종족이 살고 있다. 그는 살아남기 위해서 선한 종족과 악한 종족을 구별할 필요가 생겼는데, 그것이 그리 쉽지는 않았다. 사람들의 외모는 너무 비슷하여 그것으로 구별할 수가 없었다.
아직도 희망이 완전히 사라진 것은 아니다. 그는 기억 속에서 다음과 같이 유용한 정보를 끄집어낼 수 있었다. 그 섬에 사는 사람들은 모두 서로 잘 알고 있어서, 각자는 어떤 사람이 선한 종족이고 어떤 사람이 악한 종족인지를 구별할 수 있다. 악한 종족 사람들은 자기 마음에 드는 질문에는 대답을 하지만, 그렇지 않으면 질문한 사람을 저주하여 죽일 수도 있다. 다행히도 어떤 사람에게 다른 사람이 선한 종족인지 아닌지를 묻는 질문은 악한 종족의 비위를 거스르는 것이 아니고 따라서 그 질문은 안전하다. 선한 종족 사람들은 모두 항상 참말만 하는 참말 쟁이고, 악한 종족 사람들은 모두 항상 거짓말만 하는 거짓말쟁이이다. 두 종족 사람의 수가 전설에 나와 있어서 미리 알고 있고, 수세기 동안 그 수는 변하지 않고 있다.
로빈슨 크루소가 당신에게 도움을 청해왔다. 당신이 할 일은 그를 도와서 그의 질문에 대한 사람들의 대답을 보고 어떤 사람이 선한 종족이고 어떤 사람이 악한 종족인가를 알아내는 것이다.
입력
첫 줄에는 세 정수 n, p1, p2가 입력된다. n은 로빈슨 크루소가 물은 질문의 수이고, p1, p2는 각각 선한 종족과 악한 종족 사람의 수이다. 그 후 n개의 줄 각각은 두 정수 xi, yi와 한 단어 ai가 입력된다. xi와 yi는 섬에 사는 사람의 번호이다. 섬에 사는 사람은 1부터 p1+p2까지 미리 번호가 매겨져 있다. ai는 yes이거나 no인데, xi가 말하기를 yi가 선한 종족 사람이라고 했다면, yes이고, 그렇지 않으면, no이다. xi와 yi는 같은 사람 일 수 도 있다. 왜냐하면, "당신은 선한 종족 사람이냐?"라고 물을 수 있기 때문이다. 서로 다른 두 줄에 있는 xi와 yi 그리고 xj와 yj가 서로 같을 수도 있는데, 그것은 로빈슨 쿠르소가 흥분하여 같은 사람에게 같은 질문을 했을 수 있기 때문이다. n은 1000이하의 음이 아닌 정수이고, p1과 p2는 모두 300 이하의 음이 아닌 정수이다. 또한, 모순되는 답변은 주어지지 않는다.
출력
섬에 사는 사람을 모두 선한 종족과 악한 종족으로 분류할 만큼 충분한 정보가 주어져 있으면, 첫째 줄에 선한 종족 사람의 번호를 오름차순으로 출력한다. 만약, p1 = 0이라 출력할 번호가 없으면, 아무것도 출력하지 않는다. 충분한 정보가 주어져있지 않은 경우에는 첫 줄에 "NO"라고 출력한다.
예제 입력 1
2 1 1 1 2 no 2 1 no
예제 출력 1
NO
예제 입력 2
3 2 1 1 1 yes 2 2 yes 3 3 yes
예제 출력 2
NO
예제 입력 3
2 2 1 1 2 yes 2 3 no
예제 출력 3
1 2
예제 입력 4
5 4 3 1 2 yes 1 3 no 4 5 yes 5 6 yes 6 7 no
예제 출력 4
3 4 5 6
출처
ICPC > Regionals > Asia Pacific > Japan > Asia Regional Contest 2002 in Kanazawa G번
- 잘못된 데이터를 찾은 사람: doju
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호