cho.sh

이양식 투표

아직 제출이 없습니다시간 제한1초메모리 제한128 MB

문제

이양식 투표(transferable vote) 방식은 당선자를 단 한 명만 뽑으며, 후보가 셋 이상이더라도 당선자는 유효표의 절대 과반을 얻어야 한다. 이를 위해 각 유권자는 모든 후보를 선호 순서대로 나열한다. 후보가 $c$명이면 각 표는 1순위부터 $c$순위까지 $c$개의 선택을 담는다.

후보에는 $1$부터 $c$까지 번호가 붙는다. 한 표의 $c$개 숫자가 서로 다르지 않거나(같은 후보를 두 번 적을 수 없다) 어떤 숫자가 $1$부터 $c$의 범위를 벗어나면, 그 표는 무효표(bad ballot)이다. 무효표는 집계에서 제외되지만, 그 개수는 세어 보고한다.

유효표의 수를 $V$라 하자. 어떤 후보가 유효표의 절반을 초과하는 표, 즉 $\lfloor V/2 \rfloor + 1$표 이상을 얻는 순간 그 후보가 당선된다.

당선자는 다음 라운드를 반복하여 결정한다.

  1. 각 유효표를, 아직 탈락하지 않은 후보 중 가장 높은 순위의 후보에게 준다.
  2. 어떤 후보가 $\lfloor V/2 \rfloor + 1$표 이상을 얻었다면 그 후보가 당선된다.
  3. 그렇지 않고 남은 모든 후보의 득표수가 같다면, 그들은 모두 동점이다 — 전부 보고한다.
  4. 그 외의 경우, 최소 득표를 기록한 후보를 모두 탈락시키고 1번으로 돌아간다.

각 유효표는 $c$명의 후보 모두에 순위를 매기므로, 탈락한 후보의 표는 항상 아직 남아 있는 다음 순위 후보에게 넘어간다.

예를 들어 유권자 12명, 후보 3명인 작은 선거를 생각하자. 각 표는 표 A에 나타나 있다.

          Table A                Table B
-----------------------------    -------
Voter  First   Second  Third
       Choice  Choice  Choice
  1      1       2       4
  2      1       3       2       1  3  2
  3      3       2       1       3  2  1
  4      3       2       1       3  2  1
  5      1       2       3       1  2  3
  6      2       3       1       3  1
  7      3       2       1       3  2  1
  8      3       1       1
  9      3       2       1       3  2  1
 10      1       2       3       1  2  3
 11      1       3       2       1  3  2
 12      2       3       1       3  1

유권자 1과 8은 무효표를 던졌다(유권자 1은 존재하지 않는 후보 4를 적었고, 유권자 8은 후보 1을 두 번 적었다). 따라서 이 둘은 집계되지 않는다. 남은 유효표는 10장이므로 당선에는 최소 6표가 필요하다. 후보 1과 3이 각각 1순위 4표, 후보 2가 2표를 얻어 과반이 없다. 최소 득표인 후보 2가 탈락한다. 후보 2를 1순위로 적었던 두 표는 다음으로 살아남은 후보에게 넘어가고(표 B), 후보 3이 2표를 더 얻어 합계 6표가 되어 당선된다. (만약 유권자 12가 대신 "2 1 3"을 던졌다면 후보 1과 3이 각각 5표로 끝나 이 선거는 동점이 되었을 것이다.)

입력

입력에는 하나 이상의 선거가 주어진다. 각 선거는 후보 수 $c$와 유권자 수 $n$을 담은 한 줄로 시작한다($1 \le c \le 5$이고 유권자는 최대 100명). 이어지는 $n$개의 줄에는 각각 한 표가 공백으로 구분된 $c$개의 음이 아닌 정수로 주어지며, 해당 유권자의 1순위부터 마지막 순위까지의 선택을 나타낸다.

입력의 끝은 두 개의 0(0 0)만 있는 줄로 표시되며, 이 줄은 어떤 선거에도 속하지 않는다.

출력

각 선거에 대해 다음 형식으로 결과를 출력하며, 선거들 사이에는 빈 줄을 넣지 않고 연달아 출력한다.

  • Election #k 한 줄. 여기서 $k$는 입력에서 그 선거의 순번이다(첫 선거가 #1).
  • 무효표가 하나라도 있었다면, 세 칸 들여쓴 b bad ballot(s) 한 줄을 출력한다. 여기서 $b$는 무효표 수이며, 무효표가 없으면 이 줄은 생략한다.
  • 세 칸 들여쓴 결과 줄:
    • 후보 $w$가 당선되면 Candidate w is elected.,
    • 동점이면 The following candidates are tied: 뒤에 동점 후보 번호를 오름차순으로, 각 번호 앞에 공백 하나를 두고 나열하며 마지막 번호 뒤에도 공백 하나를 붙인다.