게리맨더링

나라마다 선거 제도는 크게 다르다. 승자독식 같은 제도에서는 최다 득표로 승자가 결정된다. 즉 가장 많은 표를 받은 후보가 당선되고, 나머지 후보는 자리를 얻지 못한다.

이런 선거에서는 "낭비된 표"가 생길 수 있다. 개념적으로 낭비된 표란 선거 결과에 영향을 주지 못한 표를 말한다. 낭비된 표의 정확한 정의는 제각각이지만, 여기서는 다음 정의를 사용한다. 유권자가 V명인 선거에서 패배한 후보에게 간 표는 모두 낭비된 표이며(이를 잃은 표라 한다), 당선된 후보에게 간 표 중 당선에 필요한 최소 과반수인 ⌊V/2⌋ + 1표를 넘는 부분도 모두 낭비된 표이다(이를 초과 표라 한다). 이 문제에서는 양당제(두 당을 A, B라 하자)를 다루며, 선거에는 항상 두 당에서 한 명씩 후보가 나온다.

한 선거구에서 두 후보가 맞붙는 간단한 예로 낭비된 표를 살펴보자. A당 후보가 100표, B당 후보가 200표를 받았다고 하자. A당의 100표는 모두 낭비된 표(A의 잃은 표)이고, B당의 49표가 낭비된 표(B의 초과 표)이다. B가 A를 누르려면 151표(⌊(100 + 200)/2⌋ + 1)가 필요하므로 남은 49표가 낭비되기 때문이다.

정치학자들은 낭비된 표로 효율성 격차를 계산한다. 효율성 격차는 낭비된 표를 요약하는 하나의 수치다. 각 선거구에서 한 명을 선출하는 선거가 여러 개 있다고 하자. 전체 선거구에서 총 V표가 투표되었고, A당의 총 낭비 표가 wA, B당의 총 낭비 표가 wB라면 효율성 격차는 다음과 같다.

E(V, WA, WB) = |WA - WB| / V .

효율성 격차가 낮으면 선거가 경쟁적이며, 각 당에서 당선된 후보 수가 각 당의 전체 득표 비율을 반영한다는 뜻이다. 효율성 격차가 높으면 게리맨더링의 징후일 수 있다. 게리맨더링이란 특정 정치적 결과에 유리하도록 선거구를 구성하는 것을 말한다. 흔한 방법 두 가지는 비슷한 유권자를 한 선거구에 "몰아넣는" 것과 여러 선거구에 "쪼개는" 것이다. 두 방법 모두 그 유권자들이 원하는 후보를 당선시키는 영향력을 줄이는 경향이 있다.

선거에서 선거구는 선거분구로 구성된다. 선거분구는 더 나눌 수 없는 유권자 집단이다. 한 선거구에 속한 모든 선거분구의 표를 합산해 그 선거구의 결과를 구한다. 이 문제에서는 여러 선거분구에 대한 정보, 즉 각 선거분구의 정당별 득표수와 그 선거분구가 어떻게 선거구로 묶였는지가 주어진다. 각 선거구마다 어느 당이 이겼는지와 각 당의 낭비된 표를 구하라. 그런 다음 전체 선거구에서 두 당 사이의 효율성 격차를 구하라.

입력은 하나의 선거를 나타낸다. 첫째 줄에 두 정수 P와 D가 주어진다. 여기서 1 ≤ P ≤ 10 000이고 1 ≤ D ≤ min(1 000, P)이다. 각각 선거분구의 수와 선거구의 수를 나타낸다. 다음 P개 줄에 선거분구에 대한 정보가 주어진다. i번째 줄에는 3개의 수가 주어진다. i번 선거분구가 속한 선거구 di(1 ≤ di ≤ D), A당 후보의 득표수(0 ≤ ai ≤ 100 000), B당 후보의 득표수(0 ≤ bi ≤ 100 000)이다. 다음이 보장된다.

• 각 선거분구 i에 대해 0 < ai + bi,
• 각 선거구에는 선거분구가 적어도 하나 배정되며,
• 어느 선거구에서도 동점은 없다.

선거구 1부터 D까지 각각에 대해 어느 당이 이겼는지 한 문자(A 또는 B)로 출력한다. 이어서 A당과 B당의 낭비된 표를 순서대로 출력한다. 모든 선거구에 대한 출력이 끝나면 전체 선거구에서 측정한 효율성 격차를 출력한다. 효율성 격차는 절대 오차 10−6 이내여야 한다.