Tävlingsprogrammering/Uppgifter/Tågväxeln

Tågväxeln

Växelholm är en väldigt liten stad med en enda byggnad – Växelholms tågstation – och en enda invånare, nämligen tågstationens föreståndare, Lokas. Lokas jobb går ut på att operera stationens manuella tågväxel, så att tågen på de två pendeltågslinjerna som passerar genom staden åker åt rätt håll. Tågen går periodiskt med m respektive n minuters mellanrum på de två linjerna, med första avgång m respektive n minuter efter midnatt. Alla tåg åker alltså ut från stationen åt samma håll men delas sedan upp på två olika spår med hjälp av en växel. Nu har JS, Järnvägarnas Stat, bestämt att Lokas ska få lön baserat på hur många gånger han ändrar växeln under ett dygn, närmare bestämt fr.o.m. 0:00 t.o.m. 23:59 (d.v.s. mellan 0 och 1439 minuter efter midnatt). Lokas ska ändra växeln enligt reglerna:

1. Om ett tåg avgår och växeln är fel inställd, ska Lokas ändra växeln till rätt spår.
2. Om två tåg avgår samma minut, så avgår först det tåg som växeln är inställd för, och sedan ska Lokas ändra växeln till det andra tågets spår.
3. I början av dygnet är växeln inställd på spåret för det tåg som avgår först.

Skriv ett program som beräknar hur många gånger som Lokas måste ändra växeln under ett helt dygn. Programmet ska fråga efter de två heltalen m och n, där m 6= n och 1 ≤ m, n ≤ 1439, som är perioden för tågens avgång, angiven i minuter.

Exempel 1

Talet m ? 450
Talet n ? 180
Antal växlingar: 5

Exempel 2

Talet m ? 500
Talet n ? 1000
Antal växlingar: 1

Exempel 3

Talet m ? 719
Talet n ? 720
Antal växlingar: 2

Exempel 4

Talet m ? 7
Talet n ? 4
Antal växlingar: 410

Lösning

Detta enkla problem kan man lösa genom att simulera tågavgångarna och räkna antalet gånger man måste byta spår. Ett exempel på en sådan lösning kan ses nedan. I denna lösningen har man två variabler som anger ordningen på för tågen på de olika spåren. Sedan vid en given tidpunkt kollar programmet vilket tåg som ska ut ur stationen härnäst. Om växlaren var ställd åt det andra hållet än tåget ska ökar man antalet växlingar med ett. Om två tåg avgår samtidigt ställs växlaren om en gång oavsett vilket spår den var inställd på tidigare. Detta pågår tills ett dygn gått (60*24=1440 minuter).

Lösning i Python:

import sys

print "Talet m ? ",
m = int(sys.stdin.readline())
print "Talet n ? ",
n = int(sys.stdin.readline())

a = 1
b = 1
t = 0
shifts = 0
shifter = '?'
while t < 1440:
    if a*m < b*n:
        t = a*m
        a += 1
        if shifter == m and t < 1440:
            shifts += 1
        shifter = n
    elif a*m > b*n:
        t = b*n
        b += 1
        if shifter == n and t < 1440:
            shifts += 1
        shifter = m
    else:
        t = a*m
        a += 1
        b += 1
        if shifter == m:
            shifter = n
        else:
            shifter = m
        if t < 1440:
            shifts += 1

print "Antal v'xlingar", shifts