PROG0382 - Baggage carousel

Bij aankomst op een luchthaven kunnen de passagiers hun koffers afhalen op een bewegende bagageband. De bagageband roteert in tegenwijzerzin en is onderverdeeld in afgescheiden compartimenten waarin telkens één koffer past. Eerst worden de koffers door een automatisch transportsysteem vanaf het vliegtuig tot bij de bagageband gebracht. Daarna plaatst een kruier de koffers één voor één op de bagageband, door telkens de volgende koffer te plaatsen in het derde lege compartiment dat bij hem voorbijkomt.

Stel bijvoorbeeld dat de kruier op die manier vijf koffers op een bagageband met acht compartimenten moet plaatsen. Voor de eenvoud hebben we de koffers gelabeld met de hoofdletters A, B, C, D en E, in de volgorde waarin ze door de kruier op de band geplaatst worden.

bagageband

Net nadat de kruier de laatste koffer (E) op de bagageband geplaatst heeft, krijgen we dus de volgende situatie.

bagageband

De band blijft daarna verder ronddraaien, zodat de situatie er een tijdje later bijvoorbeeld als volgt kan uitzien.

bagageband

Opgave

In deze opgave stellen we een bagageband voor als een lijst. De compartimenten van de bagageband corresponderen met de elementen van de lijst. Aan een element dat correspondeert met een compartiment waarin een koffer ligt, wordt een string toegekend die bestaat uit één enkel karakter (het label van de koffer). We gaan ervan uit dat alle koffers op de bagageband gelabeld zijn met een verschillend karakter. Aan een element dat correspondeert met een leeg compartiment wordt de waarde None toegekend.

De volgorde van de elementen in de lijst komt overeen met de volgorde van de compartimenten die voorbijkomen op de positie waar de kruier staat, en dit tot hij alle compartimenten heeft zien passeren. Zo wordt de bagageband die correspondeert met de middelste figuur van de inleiding voorgesteld als de lijst ['E', 'A', None, 'D', 'B', None, None, 'C']. Dezelfde bagageband, maar dan uitgelezen in de situatie uit de onderste figuur van de inleiding, wordt voorgesteld door de lijst ['B', None, None, 'C', 'E', 'A', None, 'D']. Dit zijn dus twee verschillende lijsten die in principe dezelfde bagageband voorstellen. Gevraagd wordt:

  • Schrijf een functie bagageband waaraan twee argumenten moeten doorgegeven worden: een natuurlijk getal $c$ dat aangeeft hoeveel compartimenten een bagageband heeft, en een string waarvan de karakters corresponderen met de labels van een aantal koffers die op de lege band moeten geplaatst worden in de volgorde waarin de karakters voorkomen in de string. Alle karakters in de string zijn verschillend, en het aantal karakters is kleiner of gelijk aan $c$. De functie moet een lijst teruggeven die de bagageband met $c$ compartimenten voorstelt nadat de koffers één voor één door de kruier op de bagageband geplaatst werden. Hou hierbij rekening met het feit dat de kruier telkens de volgende koffer plaatst in het derde lege compartiment dat bij hem voorbijkomt. Zorg ervoor dat het eerste element van deze lijst correspondeert met het compartiment waarin de laatste koffer geplaatst werd.
  • Schrijf een functie doorgedraaid waaraan twee lijsten moeten doorgegeven worden, die elk een bagageband voorstellen. De functie moet een Booleaanse waarde teruggeven die aangeeft of de twee gegeven lijsten al dan niet dezelfde bagageband voorstellen. Twee lijsten stellen dezelfde bagageband voor als ze evenveel compartimenten hebben, die gevuld zijn met dezelfde koffers en dit in dezelfde volgorde. Het enige verschil dat mag optreden tussen de lijsten is dat men de compartimenten op een verschillende plaats is beginnen uitlezen.

Voorbeeld

>>> bagageband(8, 'ABCDE')
['E', 'A', None, 'D', 'B', None, None, 'C']
>>> bagageband(5, 'ABCDE')
['E', 'C', 'B', 'D', 'A']

>>> doorgedraaid(['E', 'A', None, 'D', 'B', None, None, 'C'], ['B', None, None, 'C', 'E', 'A', None, 'D'])
True
>>> doorgedraaid(['E', 'A', None, 'D', 'B', None, None, 'C'], ['B', None, None, 'A', 'E', 'C', None, 'D'])
False
>>> doorgedraaid(['E', 'A', None, 'D', 'B', None, None, 'C'], ['C', 'E', 'A', None, 'D', 'B'])
False

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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.