{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:30.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/611e09d4d02f422665552f12436a12db?v\u003d1715829232\" alt\u003d\"/problems/gerrymandering/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n \n \u003c/div\u003e\n \u003cp\u003eElectoral systems across the world can vary widely. In some\n systems, such as \u003cem\u003ewinner-take-all\u003c/em\u003e, the winner is\n determined by the plurality of votes—the candidate that\n receives the most votes wins, and the loser(s) do not get a\n position.\u003c/p\u003e\n \u003cp\u003eSuch elections can have “wasted votes.” Conceptually, a\n wasted vote is a vote that did not affect the election outcome.\n While the exact definition of a wasted vote varies, we’ll adopt\n the following definition: in an election with \u003cspan class\u003d\"tex2jax_process\"\u003e$V$\u003c/span\u003e voters, every vote for a losing\n candidate is wasted (these are called \u003cem\u003elost votes\u003c/em\u003e), and\n every vote for a winning candidate beyond the strict majority\n of \u003cspan class\u003d\"tex2jax_process\"\u003e$\\lfloor V/2\\rfloor +\n 1$\u003c/span\u003e votes the candidate needs to win is wasted (these are\n called \u003cem\u003eexcess votes\u003c/em\u003e). For this problem we’ll consider\n a two-party system (let’s call the parties A and B) with\n elections that always involve one candidate from each\n party.\u003c/p\u003e\n \u003cp\u003eLet’s illustrate wasted votes with a simple example between\n two candidates in a district. Suppose that the candidate for\n party A receives \u003cspan class\u003d\"tex2jax_process\"\u003e$100$\u003c/span\u003e\n votes and the candidate for party B receives \u003cspan class\u003d\"tex2jax_process\"\u003e$200$\u003c/span\u003e votes. All \u003cspan class\u003d\"tex2jax_process\"\u003e$100$\u003c/span\u003e votes for party A are wasted\n (lost votes for A), and \u003cspan class\u003d\"tex2jax_process\"\u003e$49$\u003c/span\u003e votes for party B are wasted\n (excess votes for B). This is because B needs \u003cspan class\u003d\"tex2jax_process\"\u003e$151$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$\\lfloor (100 + 200) / 2 \\rfloor + 1$\u003c/span\u003e)\n votes to win (over A), so the remaining \u003cspan class\u003d\"tex2jax_process\"\u003e$49$\u003c/span\u003e are wasted.\u003c/p\u003e\n \u003cp\u003ePolitical scientists use wasted votes to compute the\n \u003cem\u003eefficiency gap\u003c/em\u003e, a single number that summarizes wasted\n votes. Suppose we have a number of races in different\n districts, where each district elects one person. Across all\n districts there are \u003cspan class\u003d\"tex2jax_process\"\u003e$V$\u003c/span\u003e\n total votes cast, with \u003cspan class\u003d\"tex2jax_process\"\u003e$w_\n A$\u003c/span\u003e total wasted votes for party A and \u003cspan class\u003d\"tex2jax_process\"\u003e$w_ B$\u003c/span\u003e total wasted votes for party B.\n Then the efficiency gap is:\u003c/p\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e\\[\n E(V, w_ A, w_ B) \u003d \\frac{|w_ A - w_ B|}{V}. \\]\u003c/span\u003e\n \u003cp\u003eA low efficiency gap indicates that the elections are\n competitive, and that the number of candidates elected from\n each party is representative of the total voting share for each\n party. When the efficiency gap is high, this can be an\n indication of \u003cem\u003egerrymandering\u003c/em\u003e. Gerrymandering refers to\n organizing voting districts in a way that favors a particular\n political outcome. Two common ways of doing this are to “pack”\n similar voters into districts, or “crack” them across multiple\n districts; both ways tend to diminish those voters’ influence\n in electing candidates they would like to win.\u003c/p\u003e\n \u003cp\u003eIn an election, districts are made up of precincts. A\n precinct is an indivisible group of voters. The votes for all\n precincts in a district are added together to find the results\n for that district. In this problem you are given a description\n of a number of precincts: the party vote totals for each\n precinct, and how those precincts have been grouped into\n districts. For each district, determine the party that wins and\n the wasted votes for each party. Then determine the efficiency\n gap between the two parties over all the districts.\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe input describes one election. The first line contains\n two integers \u003cspan class\u003d\"tex2jax_process\"\u003e$P$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$D$\u003c/span\u003e, where \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le P \\le 10\\, 000$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le D \\le \\min (1\\, 000,\n P)$\u003c/span\u003e. These indicate, respectively, the number of voting\n precincts and districts. Following this are \u003cspan class\u003d\"tex2jax_process\"\u003e$P$\u003c/span\u003e lines describing the precincts.\n Line \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e contains\n \u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e numbers: the district\n \u003cspan class\u003d\"tex2jax_process\"\u003e$d_ i$\u003c/span\u003e that precinct\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e is assigned to\n (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le d_ i \\le D$\u003c/span\u003e), the\n number of votes for the candidate from party A (\u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\le a_ i \\le 100\\, 000$\u003c/span\u003e), and the\n number of votes for the candidate from party B (\u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\le b_ i \\le 100\\, 000$\u003c/span\u003e). It is\n guaranteed that:\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003efor each precinct \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$0 \u0026lt; a_ i + b_ i$\u003c/span\u003e,\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eeach district is assigned at least one precinct, and\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003ethere are no ties within any district.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eFor each of the districts from \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$D$\u003c/span\u003e, print which party wins (a single\n character, either \u003ctt class\u003d\"ttfamily\"\u003eA\u003c/tt\u003e or \u003ctt class\u003d\"ttfamily\"\u003eB\u003c/tt\u003e). Then print the number of wasted votes for\n party A and for party B, in order. Finally, after reporting on\n all the districts, print the efficiency gap as measured over\n all the districts. The efficiency gap should be accurate to\n within an absolute error of \u003cspan class\u003d\"tex2jax_process\"\u003e$10^{-6}$\u003c/span\u003e.\u003c/p\u003e\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 3\n1 100 200\n2 100 99\n3 100 50\n3 100 50\n2 100 98\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eB 100 49\nA 1 197\nA 49 100\n0.1965897693\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 4\n3 100 99\n2 100 99\n1 100 99\n4 100 99\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eA 0 99\nA 0 99\nA 0 99\nA 0 99\n0.4974874372\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 3\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 4\n4 99 100\n1 100 99\n3 100 99\n2 99 100\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eA 0 99\nB 99 0\nA 0 99\nB 99 0\n0.0000000000\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}