blackbee4   1년 전

문제

전 세계의 선거 시스템은 매우 다양할 수 있습니다. winner-takes-all(승자 독식)과 같은 일부 시스템에서는 다수의 표에 따라 승자가 결정되며, 가장 많은 표를 얻은 후보가 승리하고 패자는 자리를 얻지 못합니다.

이러한 선거는 "사표(낭비된 표)"를 가질 수 있습니다. 개념적으로 사표는 선거 결과에 영향을 미치지 않는 표를 의미합니다. 사표의 정확한 정의는 다양하지만, 우리는 다음과 같은 정의를 채택할 것입니다: 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의 절대 오차 범위 내에서 정확해야 합니다.

댓글을 작성하려면 로그인해야 합니다.