Problem C
Gerrymandering

Electoral systems across the world can vary widely. In some systems, such as winner-take-all, the winner is determined by the plurality of votes—the candidate that receives the most votes wins, and the loser(s) do not get a position.
Such elections can have “wasted votes.” Conceptually, a
wasted vote is a vote that did not affect the election outcome.
While the exact definition of a wasted vote varies, we’ll adopt
the following definition: in an election with
Let’s illustrate wasted votes with a simple example between
two candidates in a district. Suppose that the candidate for
party A receives
Political scientists use wasted votes to compute the
efficiency gap, a single number that summarizes wasted
votes. Suppose we have a number of races in different
districts, where each district elects one person. Across all
districts there are
A low efficiency gap indicates that the elections are competitive, and that the number of candidates elected from each party is representative of the total voting share for each party. When the efficiency gap is high, this can be an indication of gerrymandering. Gerrymandering refers to organizing voting districts in a way that favors a particular political outcome. Two common ways of doing this are to “pack” similar voters into districts, or “crack” them across multiple districts; both ways tend to diminish those voters’ influence in electing candidates they would like to win.
In an election, districts are made up of precincts. A precinct is an indivisible group of voters. The votes for all precincts in a district are added together to find the results for that district. In this problem you are given a description of a number of precincts: the party vote totals for each precinct, and how those precincts have been grouped into districts. For each district, determine the party that wins and the wasted votes for each party. Then determine the efficiency gap between the two parties over all the districts.
Input
The input describes one election. The first line contains
two integers
-
for each precinct
, , -
each district is assigned at least one precinct, and
-
there are no ties within any district.
Output
For each of the districts from
Sample Input 1 | Sample Output 1 |
---|---|
5 3 1 100 200 2 100 99 3 100 50 3 100 50 2 100 98 |
B 100 49 A 1 197 A 49 100 0.1965897693 |
Sample Input 2 | Sample Output 2 |
---|---|
4 4 3 100 99 2 100 99 1 100 99 4 100 99 |
A 0 99 A 0 99 A 0 99 A 0 99 0.4974874372 |
Sample Input 3 | Sample Output 3 |
---|---|
4 4 4 99 100 1 100 99 3 100 99 2 99 100 |
A 0 99 B 99 0 A 0 99 B 99 0 0.0000000000 |