4419번 - 호주식 투표법 출처다국어분류
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 105 | 21 | 18 | 23.077% |
문제
호주식 투표법은 선호도 순서대로 후보들의 순위를 매기는 것이다. 처음에는 첫 번째로 선택된 후보들의 표만 세고, 만약 한 후보가 절반을 넘는(초과) 표를 얻으면 그 후보가 당선된다. 어느 후보도 절반을 넘는 표를 얻지 못하면, 첫 번째로 선택된 표 수가 가장 적은 후보들을 탈락시킨다. 그리고 이 (탈락된 후보를 첫 번째로 선택한)표에서 탈락된 후보들을 제외한 나머지 후보들 중 가장 높은 선호도를 가진 후보에게 표를 더해준다. 이 과정을 한 후보가 절반이 넘는 표를 얻거나, 모든 후보가 동점이 될 때까지 반복한다.
입력
입력의 첫 째줄은 n <= 20을 만족하는 정수이고 후보자들의 수를 나타낸다. 그 다음 n개의 입력은 후보자들의 이름을 순서대로 나타낸다. 이름은 최대 80개의 문자로 이루어져 있고 표현될 수 있는 모든 문자를 포함한다. 최대 1000개의 줄이 입력되는데, 각각은 투표 용지를 의미한다. 즉, 각 줄마다 1부터 n까지의 숫자를 순서대로 가지고 있다. 첫 번째 숫자는 첫 번째로 선호하는 후보의 번호를 나타내고, 두 번째 숫자는 두 번째로 선호하는 후보의 번호를 나타내고 나머지도 그와 같다.
출력
출력은 당선된 후보의 이름 하나이거나, 동점자들의 이름 여러 줄이 될 수 있다.
예제 입력 1
3 John Doe Jane Smith Sirhan Sirhan 1 2 3 2 1 3 2 3 1 1 2 3 3 1 2
예제 출력 1
John Doe
출처
Contest > Waterloo's local Programming Contests > 17 October, 1998 D번
- 문제를 번역한 사람: dritte
© 2020 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 5층 509호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호
