Tävlingsprogrammering/Uppgifter/Postiljoner

Postiljoner

Företaget Posten AB ska lägga schema för sina anställda postiljoner. Dessa jobbar alltid heltid, 4 dagar i följd. Däremot är det schemaläggarens ansvar att säga vilken veckodag postiljonen ska börja jobba. En anställd kan t.ex. jobba måndag–torsdag, en annan anställd kan jobba lördag–tisdag (det finns inget helg-begrepp i uppgiften).

Eftersom mängden post varierar, kräver varje veckodag ett visst antal anställda som är tillgängliga.

Skriv ett program som frågar efter de 7 veckodagarnas belastning och beräknar det minsta antalet postiljoner som måste vara anställda. Belastningen för en arbetsdag kommer aldrig överstiga 200.

Exempel 1

Måndag ? 1
Tisdag ? 2
Onsdag ? 2
Torsdag ? 2
Fredag ? 2
Lördag ? 2
Söndag ? 1

Svar

Antal postiljoner: 3

Förklaring: Postiljonerna kan t.ex. börja på tisdag, onsdag och lördag.

Exempel 2

Måndag ? 7
Tisdag ? 10
Onsdag ? 2
Torsdag ? 4
Fredag ? 5
Lördag ? 2
Söndag ? 1

Svar

Antal postiljoner: 11

Förklaring: Du kan t.ex. lägga 5 postiljoner på måndag, 4 på tisdag och en vardera på fredag och lördag.

Exempel 3

Måndag ? 48
Tisdag ? 81
Onsdag ? 75
Torsdag ? 76
Fredag ? 76
Lördag ? 59
Söndag ? 73

Svar

Antal postiljoner: 122

Lösning

En greedy-lösning fungerar inte, dvs. en sorts lösning som för varje postiljon försöker hitta den för närvarande bästa dagen, och väljer den. Det man istället får göra är att loopa över alla möjligheter av postiljoner på tre närliggande dagar. Dvs. 201*201*201 fall. När man har hur många postiljoner som arbetar på tre närliggande dagar faller nämligen resten av dagarna ut automatiskt. När man har räknat postiljoner för varje fall skriver man helt enkelt ut det fallet som innehöll minst antal postiljoner. Vill man vara extra cool kan man se detta problem som något inom Linjär Programmering, och löses då med Simplex algoritm blixtsnabbt.

En lösning i Haskell. För att programmet ska köras tillräckligt fort måste det kompileras med -O2 flaggan. Observera att det är av yttersta vikt att vi talar om att getInt ska returnera en Int, annars kommer Haskell defaulta till Integer och programmet kommer att gå långsammare.

-- Postiljoner
module Main where

getInt :: IO Int
getInt = fmap read getLine

main = putStr "Mandag ? " >> getInt >>= \m ->
	putStr "Tisdag ? " >> getInt >>= \ti ->
	putStr "Onsdag ? " >> getInt >>= \o ->
	putStr "Torsdag ? " >> getInt >>= \to ->
	putStr "Fredag ? " >> getInt >>= \f ->
	putStr "Lordag ? " >> getInt >>= \l ->
	putStr "Sondag ? " >> getInt >>= \s ->
	putStrLn.("\nAntal postiljoner: " ++).show $
	minimum [solve a b c [m,ti,o,to,f,l,s] | a <- [0..m], b <- [0..ti], c <- [0..o]]
	
solve a b c [m,ti,o,to,f,l,s] = a+b+c+tor+fre+lor+rest
	where
	tor = max 0 (to-a-b-c)
	fre = max 0 (f-b-c-tor)
	lor = max 0 (l-c-tor-fre)
	rest = maximum [0, s-tor-fre-lor, m-a-lor-fre, ti-b-a-lor, o-c-b-a]