SPOJ.com - Problem PROG0514

PROG0514 - The last marble

no tags

An urn contains 75 white marbles and 150 black marbles. An inexhaustible pile of black marbles is also available. Repeatedly apply the following two-step operation: first withdraw two marbles at random from the urn, and then

if both are black, put one of them back in the urn and throw the other away
if one is black and the other white, put the white one back and throw the black one away
if both are white, throw both away and put a black marble from the pile into the urn

Because the urn loses a marble at each step, eventually it will contain a single marble. What color is that last marble?

Assignment

In this exercise, an urn containing $w$ white and $b$ black marbles is represented as a sequence (a list or a tuple) that contains $w$ occurrences of the string white and $b$ occurrences of the string black. Although there is no predefined order of the marbles contained in the urn, its representation as a list or a tuple imposes an order on the marbles that makes it possible to indicate a particular marble at a given position. Your task:

Write a function fill that takes an integer $n \in \mathbb{N}$. The function must return an urn (a list) that contains $n$ marbles in total. The function must guarantee that the color of each marble in the urn is randomly chosen between the colors black and white, independent of the position of the marbles in the list that represents the urn.
Write a function pick that takes an urn (a list or a tuple) containing black and white marbles. The function must return a tuple containing two integers that indicate two different positions into the sequence representing the urn. Make sure the function does not alter the argument passed to the function.
Write a function remove that takes three arguments. The third argument represents an urn (a list) containing black and white marbles, and the first and second argument indicate different positions of two marbles contained in the list that represents the urn. The function must remove the two marbles at the given positions in the list representing the urn, and add a new marble to the end of the list whose color is determined by the colors of the marbles withdrawn from the list using the procedure described in the introduction.
Write a function last that takes an urn (a list or a tuple) containing black and white marbles. The function must return the color (string) of the last marble that remains in the urn after having executed the procedure described in the introduction. Make sure the function does not alter the argument passed to the function.

Example

>>> urn = fill(10)
>>> urn
['white', 'white', 'black', 'black', 'black', 'white', 'white', 'white', 'white', 'black']
>>> marble1, marble2 = pick(urn)
>>> marble1, marble2
(1, 9)
>>> remove(marble1, marble2, urn)
>>> urn
['white', 'black', 'black', 'black', 'white', 'white', 'white', 'white', 'white']
>>> last(urn)
'black'

Voor jouw staat een urne die 75 witte knikkers en 150 zwarte knikkers bevat. Daarnaast beschik je ook nog over een onuitputtelijke voorraad zwarte knikkers. Herhaal de volgende tweestapsprocedure: eerst haal je willekeurig twee knikkers uit de urne, en daarna

als beide zwart zijn, stop je er één terug en gooi je de andere weg
als de ene zwart is en de andere wit, stop je de witte terug en gooi je de zwarte weg
als beide wit zijn, gooi je ze beide weg en stop je een zwarte uit de voorraad terug

Omdat de urne na elke stap één knikker minder bevat, zal er uiteindelijk nog slechts één knikker overblijven. Welke kleur heeft deze knikker?

Opgave

In deze opgave stellen we een urne met $w$ witte en $z$ zwarte knikkers voor als een sequentie (een lijst of een tuple) die $w$ keer de string wit bevat en $z$ keer de string zwart. De volgorde waarin de knikkers in de urne voorkomen speelt geen rol, maar door de voorstelling als een lijst of een tuple hebben de knikkers wel een opgelegde volgorde waardoor we een knikker op een bepaalde positie kunnen aangeven. Gevraagd wordt.

Schrijf een functie vullen waaraan een getal $n \in \mathbb{N}$ moet doorgegeven worden. De functie moet een urne (een lijst) teruggeven die in totaal $n$ knikkers bevat. De functie moet ervoor zorgen dat elke knikker in de urne een willekeurig gekozen kleur krijgt (zwart of wit), onafhankelijk van de positie van de knikkers in de lijst die de urne voorstelt.
Schrijf een functie kiezen waaraan een urne (een lijst of een tuple) met zwarte en witte knikkers moet doorgegeven worden. De functie moet een tuple met twee willekeurig gekozen natuurlijke getallen teruggeven, die twee verschillende posities aanduiden in de sequentie die de urne voorstelt. Het argument dat aan de functie doorgegeven wordt, mag hierbij niet gewijzigd worden.
Schrijf een functie verwijderen waaraan drie argumenten moeten doorgegeven worden. Het derde argument stelt een urne (een lijst) met zwarte en witte knikkers voor, en de eerste twee argumenten duiden de positie van twee knikkers aan in de lijst die de urne voorstelt. De functie moet de knikkers op de twee aangegeven positie verwijderen uit de lijst die de urne voorstelt, en achteraan de lijst een nieuwe knikker toevoegen waarvan de kleur bepaald wordt door de kleur van de verwijderde knikkers zoals aangegeven in de inleiding.
Schrijf een functie laatste waaraan een urne (een lijst of een tuple) met zwarte en witte knikkers moet doorgegeven worden. De functie moet de kleur (string) teruggeven van de laatste knikker die in de urne overblijft, als de procedure wordt uitgevoerd die in de inleiding staat beschreven. Het argument dat aan de functie doorgegeven wordt, mag hierbij niet gewijzigd worden.

Voorbeeld

>>> urne = vullen(10)
>>> urne
['wit', 'wit', 'zwart', 'zwart', 'zwart', 'wit', 'wit', 'wit', 'wit', 'zwart']
>>> knikker1, knikker2 = kiezen(urne)
>>> knikker1, knikker2
(1, 9)
>>> verwijderen(knikker1, knikker2, urne)
>>> urne
['wit', 'zwart', 'zwart', 'zwart', 'wit', 'wit', 'wit', 'wit', 'wit']
>>> laatste(urne)
'zwart'

Submit solution!

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