Tävlingsprogrammering/Uppgifter/Busskortet

Busskortet

Du ska köpa ett busskort. Det är ett påtankningskort som du laddar med pengar, därefter kan du åka på kortet tills pengarna tagit slut. Du vet att du ska åka för K kronor, där K ≤ 10000. Att ladda kortet tar sin tid eftersom du endast kan ladda kortet med 500, 200 eller 100 kr i taget. Du har för tillfället bråttom och vill därför utföra så litet antal transaktioner som möjligt, men aldrig tanka på mer pengar än nödvändigt.

Om du ska åka för 800 kronor ska du alltså först ladda med 500, sen med 200, därefter med 100 kr. Om du däremot ska åka för 850 kronor ska du först ladda med 500 och därefter ladda med 200 två gånger. Visserligen går 50 kronor till spillo, men det är ändå det bästa alternativet.

Skriv ett program som beräknar det minsta antalet transaktioner du behöver göra.

Körningsexempel 1:

Åka för ? 850
Antal transaktioner: 3

Körningsexempel 2:

Åka för ? 1800
Antal transaktioner: 5

Lösning

Här gäller det helt enkelt att bara implementera en enkel girig algoritm. Kan man ladda med 500 kr, så bör man göra det, om inte så 200 kr, om inte det så får vi ladda med 100 kr. Detta är enkelt att utföra för alla tal jämnt delbara med 100, men hur bör man göra om talet inte är det? Om talet t.ex. är 7321? Ja då gäller det att inse att den minsta förlusten som kan göras är den när man laddat till sig summan 7400 kr. Och då blir problemet plötsligt igen löjligt enkelt att lösa, eftersom det lite mer komplicerade fallet 7321 kr har samma lösning som det superenkla fallet 7400 kr.

Här nedan följer en lösning i Java.

import java.util.*;

public class Busskortet
{
	public static void main(String [] klein)
	{
		Scanner scan = new Scanner(System.in);

		System.out.print("Åka för: ");
		int K = scan.nextInt();

		//Antalet transaktioner som krävs.
		int svar = 0;

		//Hur mycket pengar vi har för tillfället.
		int summa = 0;

		//Hur mycket vi som minst kan lyckas överstiga K-värdet.
		//Om vi ska ha 739, så är 800 den minsta summan vi kan
		//komma upp i som är större än 739, vilket ger ett överskott på 61 kr.
		// %100 igen på slutet ifall K%100 skulle råka bli 0.
		int overskott = (100-(K%100))%100;

		//Kör på tills vi har pengarna vi vill ha.
		while(summa<K)
		{
			//Om vi kan ladda 500 och det nya värdet inte överstiger så
			//mycket vi ska åka för + så mycket vi minst kan hamna över den
			//önskade summan, så bör vi givetvis ladda 500.
			if(summa+500<=K+overskott)
			{
				summa += 500; //Ökar summan.
				svar++; //Vi har utfört en transaktion.
			}
			else if(summa+200<=K+overskott) //Om inte testa med 200 istället.
			{
				summa += 200;
				svar++;
			}
			else //Och sista valet blir givetvis 100.
			{
				summa += 100;
				svar++;
			}
		}

		//Skriver ut svaret.
		System.out.println("Antal transaktioner: " + svar);
	}
}

Snajsig lösning i Haskell. Observera hur vi lyckas klara oss undan exekveringsfel p.g.a. att Haskell är latevaluerat. Skulle vi använt oss av takeWhile (0 <=) istället för takeWhile (0 <) skulle vi få exekveringsfel, eftersom funktionen buy då skulle behöva generera ett negativt tal, vilket den inte gör.

-- Busskortet
module Main where
import IO
import Data.List

main = do {
	putStr "Aka for ? ";
	k <- getLine;
	
	putStrLn $ "Antal transaktioner: " ++ (show $ length $ takeWhile (0 <) $ iterate buy (div (read k + 99) 100 * 100))
}

buy :: Int -> Int
buy k = head $ filter (0 <=) [k-500, k-200, k-100]