시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 128 MB | 164 | 31 | 24 | 24.242% |
콩도르세 승자는 선거에서 다른 모든 후보를 1:1로 이길 수 있는 후보자이다. 콩도르세 승자는 투표자가 자신이 선호하는 순서대로 투표자를 모두 적는 투표 방식에서만 결정할 수 있다. 이때 사용하는 투표용지를 선호 리스트라고 한다.
예를 들어, 후보가 3명 A, B, C이고, 투표자가 세 명일 때 선호 리스트에 ABC, BAC, CBA와 같이 적혀져있다고 하자. 이 경우에 콩도르세 승자는 B이다. B는 A를 2번 (2, 3)이기고, C를 2번 (1, 2) 이긴다.
콩도르세 투표 시스템에서 당선자는 콩도르세 승자이다. 만약 위의 예제가 보통 투표 방식(1등만)을 사용한다면, 모두 동점이 된다. 콩도르세 투표에서 콩도르세 승자는 한 명을 넘을 수 없다. 하지만, 콩도르세 승자가 없을 수도 있다.
선호 리스트가 주어졌을 때, 콩도르세 승자를 구하는 프로그램을 작성하시오.
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 선호 리스트의 수 b와 후보자의 수 c가 주어진다. (1 ≤ b ≤ 500, 1 ≤ c ≤ 2500) 후보자는 0번부터 c-1번까지 번호가 매겨져 있다. 다음 줄부터 b개 줄에는 각 선호 리스트에 적혀있는 후보자가 순서대로 주어진다.
입력의 마지막 줄에는 0 0이 주어진다.
각 테스트 케이스에 대해서 콩도르세 승자를 출력한다. 만약, 승자가 없는 경우에는 No Condorcet winner를 출력한다.
3 3 0 1 2 1 0 2 2 1 0 3 3 0 1 2 1 2 0 2 0 1 0 0
Case 1: 1 Case 2: No Condorcet winner
ICPC > Regionals > North America > East Central North America Regional > 2011 East Central Regional Contest C번