SPOJ.com - Problem PROG0291

PROG0291 - Electors

no tags

The president of the United States is not chosen directly. Actually, on the day of the elections, it is not the president that gets chosen, but the college that is going to choose the president. The electoral college consists of 538 electors. That is the same number as the amount of senators and representatives, completed with three extra seats for Washington D.C. Because the number of delegates differs in each state, there is a difference in number of electors per state. The minimum number of electors per state is three, since every state has two senators and at least one representative.

Most state laws establish a winner-take-all system, wherein the ticket that wins a plurality of votes wins all of that state's allocated electoral votes, and thus has their slate of electors chosen to vote in the Electoral College. Maine and Nebraska do not use this method, opting instead to give two electoral votes to the statewide winner and one electoral vote to the winner of each Congressional district. For this assignment however, we will ignore this exception and we presume that the first past the post principle applies to all states.

Map showing the construction of the Electoral College after the presidential elections of 2008. The democratic candidate Barack Obama won the election in 28 states and Washington, D.C. (indicated with blue), pulling in 365 electors. The republican candidate John McCain won the election in 22 states (indicated in red), pulling in 173 electors. Nebraska split its electoral vote, because Obama won the election in Nebraska's second district. The other four electors of this state went to McCain.

The two largest parties in the United States are the Democratic Party and the Republican Party. Furthermore, there are some smaller parties (the Liberal Party, the Green Party and the Constitutional Party, amongst others), but we will not take this into account for this assignment.

After every census, that is taken in the U.S. every ten years, the number of delegates and electors per state is adapted. We use the following order for the states: California, Texas, Florida, New York, Illinois, Pennsylvania, Ohio, Georgia, Michigan, North Carolina, New Jersey, Virginia, Washington, Arizona, Indiana, Massachusetts, Tennessee, Maryland, Minnesota, Missouri, Wisconsin, Alabama, Colorado, South Carolina, Kentucky, Louisiana, Connecticut, Oklahoma, Oregon, Arkansas, Iowa, Kansas, Mississippi, Nevada, Utah, Nebraska, New Mexico, West Virginia, Hawaï, Idaho, Maine, New Hampshire, Rhode Island, Alaska, Delaware, District of Columbia, Montana, North Dakota, South Dakota, Vermont and Wyoming. In the same order, the number of electors per state from 2010 until 2020 is: 55, 38, 29, 29, 20, 20, 18, 16, 16, 15, 14, 13, 12, 11, 11, 11, 11, 10, 10, 10, 10, 9, 9, 9, 8, 8, 7, 7, 7, 6, 6, 6, 6, 6, 6, 5, 5, 5, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3 and 3.

Assignment

Write a function electors to which a list of tuples should be given. Every tuple contains two whole numbers, that represent the number of votes for the Democratic Party — resp. the Republican Party — in a certain state. The function should print a list of tuples, where a tuple indicates whether the electors are for the Democratic Party (first element is True) or for the Republican Party (first element is False), and the total amount of electors in that state (second element of the tuple). All this is determined based on the distribution of electors for the period 2010-2020. However, another argument called distribution can be given to the function. If this is the case, this argument is used to determine the distribution of the electors.
Use the function electors in order to write a function result. This function takes the same argument as the function above, but it returns only one tuple. This tuple contains in the first position the number of electors for the Democratic Party and in the second position the number of electors of the Republican Party.

Example

>>> votes2008 = [
...     (8274473, 5011781), (3528633, 4479328), (4282074, 4045624),
...     (4804701, 2752728), (3419348, 2031179), (3276363, 2655885),
...     (2940044, 2677820), (1844123, 2048759), (2872579, 2048639),
...     (2142651, 2128474), (2215422, 1613207), (1959532, 1725005),
...     (1750848, 1229216), (1034707, 1230111), (1374039, 1345648),
...     (1904097, 1108854), (1087437, 1479178), (1629467, 959862),
...     (1573354, 1275409), (1441911, 1445814), (1677211, 1262393),
...     (813479, 1266546), (1288576, 1073589), (862449, 1034896),
...     (751985, 1048462), (782989, 1148275), (997772, 629428),
...     (502496, 960165), (1037291, 738475), (422310, 638017),
...     (828940, 682379), (514765, 699655), (554662, 724597), (533736, 412827),
...     (327670, 596030), (333319, 452979), (472422, 346832), (303857, 397466),
...     (325871, 120566), (236440, 403012), (421923, 295273), (384826, 316534),
...     (296571, 165391), (123594, 193841), (255459, 152374), (245800, 17367),
...     (231667, 242763), (141278, 168601), (170924, 203054), (219262, 98974),
...     (82868, 164958)
... ]

>>> electors(votes2008)
... [
...     (True, 55), (False, 38), (True, 29), (True, 29), (True, 20), (True, 20),
...     (True, 18), (False, 16), (True, 16), (True, 15), (True, 14), (True, 13),
...     (True, 12), (False, 11), (True, 11), (True, 11), (False, 11), (True, 10),
...     (True, 10), (False, 10), (True, 10), (False, 9), (True, 9), (False, 9),
...     (False, 8), (False, 8), (True, 7), (False, 7), (True, 7), (False, 6),
... 	(True, 6), (False, 6), (False, 6), (True, 6), (False, 6), (False, 5),
... 	(True, 5), (False, 5), (True, 4), (False, 4), (True, 4), (True, 4),
... 	(True, 4), (False, 3), (True, 3), (True, 3), (False, 3), (False, 3),
...     (False, 3), (True, 3), (False, 3)
... ]

>>> result(votes2008)
(358, 180)

>>> distribution2000 = [
...     55, 34, 27, 31, 21, 21, 20, 15, 17, 15, 15, 13, 11, 10, 11, 12, 11, 10,
...     10, 11, 10, 9, 9, 8, 8, 9, 7, 7, 7, 6, 7, 6, 6, 5, 5, 5, 5, 5, 4, 4, 4,
...     4, 4, 3, 3, 3, 3, 3, 3, 3, 3
... ]

>>> result(votes2008, distribution2000)
(364, 174)

In de Verenigde Staten wordt de president niet rechtstreeks gekozen. Feitelijk wordt op de dag van de verkiezingen niet de president gekozen, maar het college dat hem gaat kiezen. Het kiescollege bestaat uit 538 kiesmannen. Dat is evenveel als het aantal senatoren en leden van het Huis van Afgevaardigden, aangevuld met drie extra zetels voor Washington D.C.. Omdat het aantal afgevaardigden per staat verschillend is, is ook het aantal kiesmannen per staat verschillend. Het minimum aantal voor een staat is drie, omdat iedere staat twee senatoren heeft en ten minste één afgevaardigde.

De verkiezing door de kiesmannen gaat in de meeste staten volgens het first past the post principe. Dat wil zeggen dat degene die in een bepaalde staat de meeste stemmen haalt, alle kiesmannen van die staat binnenhaalt. Uitzonderingen zijn de staten Maine en Nebraska. Daar worden twee kiesmannen op deze wijze gekozen; de andere (twee in Maine, drie in Nebraska) worden per congresdistrict gekozen. Voor deze opgave gaan we deze twee uitzonderingen echter negeren en gaan we ervan uit dat overal het first past the post principe toegepast wordt.

Kaart die de samenstelling van het Electoral College weergeeft na de Amerikaanse presidentsverkiezingen van 2008. De democratische kandidaat Barack Obama won de verkiezing in 28 staten en Washington, D.C. (aangegeven in het blauw) om daarmee 365 kiesmannen binnen te halen. De republikeinse kandidaat John McCain won de verkiezing in 22 staten (aangegeven in het rood) om daarmee 173 kiesmannen achter zich te scharen. Nebraska splitste zijn electorale stem doordat Obama de verkiezing won in Nebraska's tweede congesdistrict. De andere vier kiesmannen van deze staat gingen naar McCain.

De twee grootste partijen in de Verenigde Staten zijn de Democratische Partij en de Republikeinse Partij. Daarnaast zijn er ook nog enkele kleinere partijen (o.a. de Libertarische Partij, de Groene Partij en de Constitutionele Partij), maar deze gaan we buiten beschouwing laten voor deze opgave.

Na iedere volkstelling, die in de VS elke tien jaar wordt gehouden, worden de aantallen afgevaardigden, en derhalve kiesmannen, per staat aangepast. We gebruiken de volgende volgorde voor de staten: Californië, Texas, Florida, New York, Illinois, Pennsylvania, Ohio, Georgia, Michigan, North Carolina, New Jersey, Virginia, Washington, Arizona, Indiana, Massachusetts, Tennessee, Maryland, Minnesota, Missouri, Wisconsin, Alabama, Colorado, South Carolina, Kentucky, Louisiana, Connecticut, Oklahoma, Oregon, Arkansas, Iowa, Kansas, Mississippi, Nevada, Utah, Nebraska, New Mexico, West Virginia, HawaïÂ�, Idaho, Maine, New Hampshire, Rhode Island, Alaska, Delaware, District of Columbia, Montana, North Dakota, South Dakota, Vermont en Wyoming. Met deze volgorde zijn de aantal kiesmannen per staat voor de periode van 2010 tot 2020 de volgende: 55, 38, 29, 29, 20, 20, 18, 16, 16, 15, 14, 13, 12, 11, 11, 11, 11, 10, 10, 10, 10, 9, 9, 9, 8, 8, 7, 7, 7, 6, 6, 6, 6, 6, 6, 5, 5, 5, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3 en 3.

Opgave

Schrijf een functie kiesmannen waaraan een lijst van tuples moet doorgegeven worden. Elk tuple bevat twee gehele getallen, die staan voor het aantal stemmen die de Democratische Partij — resp. de Republikeinse Partij — in een bepaalde staat heeft behaald. De functie moet een lijst van tuples van lengte twee teruggeven, waarbij een tuple voor een bepaalde staat aangeeft of de kiesmannen voor de Democratische Partij zijn (eerste element is True) of voor de Republikeinse Partij (eerste element is False), en hoeveel kiesmannen er zijn in die staat (tweede element van het tuple). Dit alles wordt bepaald op basis van de verdeling van de kiesmannen voor de periode 2010-2020. Er kan echter een tweede argument met als naam verdeling aan de functie meegegeven worden. Als dat het geval is, dan wordt dit argument gebruikt om de verdeling van de kiesmannen te bepalen.
Gebruik de functie kiesmannen om een functie uitslag te schrijven. Deze functie neemt dezelfde argumenten als de vorige functie, maar geeft slechts één tuple terug. Dit tuple bevat op de eerste positie het aantal kiesmannen voor de Democratische Partij en op de tweede positie het aantal kiesmannen voor de Republikeinse Partij.

Voorbeeld

>>> stemmen2008 = [
...     (8274473, 5011781), (3528633, 4479328), (4282074, 4045624),
...     (4804701, 2752728), (3419348, 2031179), (3276363, 2655885),
...     (2940044, 2677820), (1844123, 2048759), (2872579, 2048639),
...     (2142651, 2128474), (2215422, 1613207), (1959532, 1725005),
...     (1750848, 1229216), (1034707, 1230111), (1374039, 1345648),
...     (1904097, 1108854), (1087437, 1479178), (1629467, 959862),
...     (1573354, 1275409), (1441911, 1445814), (1677211, 1262393),
...     (813479, 1266546), (1288576, 1073589), (862449, 1034896),
...     (751985, 1048462), (782989, 1148275), (997772, 629428),
...     (502496, 960165), (1037291, 738475), (422310, 638017),
...     (828940, 682379), (514765, 699655), (554662, 724597), (533736, 412827),
...     (327670, 596030), (333319, 452979), (472422, 346832), (303857, 397466),
...     (325871, 120566), (236440, 403012), (421923, 295273), (384826, 316534),
...     (296571, 165391), (123594, 193841), (255459, 152374), (245800, 17367),
...     (231667, 242763), (141278, 168601), (170924, 203054), (219262, 98974),
...     (82868, 164958)
... ]

>>> kiesmannen(stemmen2008)
... [
...     (True, 55), (False, 38), (True, 29), (True, 29), (True, 20), (True, 20),
...     (True, 18), (False, 16), (True, 16), (True, 15), (True, 14), (True, 13),
...     (True, 12), (False, 11), (True, 11), (True, 11), (False, 11), (True, 10),
...     (True, 10), (False, 10), (True, 10), (False, 9), (True, 9), (False, 9),
...     (False, 8), (False, 8), (True, 7), (False, 7), (True, 7), (False, 6),
... 	(True, 6), (False, 6), (False, 6), (True, 6), (False, 6), (False, 5),
... 	(True, 5), (False, 5), (True, 4), (False, 4), (True, 4), (True, 4),
... 	(True, 4), (False, 3), (True, 3), (True, 3), (False, 3), (False, 3),
...     (False, 3), (True, 3), (False, 3)
... ]

>>> uitslag(stemmen2008)
(358, 180)

>>> verdeling2000 = [
...     55, 34, 27, 31, 21, 21, 20, 15, 17, 15, 15, 13, 11, 10, 11, 12, 11, 10,
...     10, 11, 10, 9, 9, 8, 8, 9, 7, 7, 7, 6, 7, 6, 6, 5, 5, 5, 5, 5, 4, 4, 4,
...     4, 4, 3, 3, 3, 3, 3, 3, 3, 3
... ]

>>> uitslag(stemmen2008, verdeling2000)
(364, 174)

Submit solution!

Added by:	Peter Dawyndt
Date:	2012-11-07
Time limit:	10s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	PY_NBC
Resource:	None