Tävlingsprogrammering/Uppgifter/Brevlådeplacering

Brevlådeplacering

Utmed en väg ligger hus (högst 20 stycken) utspridda vid givna positioner (angivna i meter mellan 0 och 10000). För att spara tid vid utdelningen vill Posten att husens brevlådor ska grupperas ihop vid speciella platser utmed vägen.Man vill dock garantera att inget hus får längre än 200 meter till sin brevlåda. Du ska skriva ett program som beräknar det minimala antalet brevlådeplatser som behövs.

Körningsexempel:

Antal hus ? 6
Position för hus 1 ? 1120
Position för hus 2 ? 256
Position för hus 3 ? 440
Position för hus 4 ? 684
Position för hus 5 ? 380
Position för hus 6 ? 1040
Antal platser: 3

Lösning

Hur ska man angripa detta problem? Ett sätt är att testa alla eller många lösningar. Men det är inte nödvändigt; det finns nämnligen ett enklare sätt.

Om det sista huset befinner sig exempelvis vid position 1000 så är det ju lika bra att placera brevlådan vid position 800. Då¨har vi tillgodosett alla hus vars position är >= 600. Sen är det bara att fortsätta så tills det inte är några hus kvar att betjäna.

# -*- coding: cp1252 -*-

n = input("Antal hus? ")

husen = [] # Lista över positionerna för alla hus

for hus in range(n):
    pos = input("Position för hus " + str(hus + 1) + " ? ")
    husen.append(pos) # Lägg till i huslistan.

i = 0 # Antal postlådor

# Medan det finns hus kvar
while husen:
    i += 1 # Vi placerar ut en till postlåda

    pos = husen.pop() # Ta bort det sista huset i huslistan

    husen = [hus for hus in husen if hus < pos - 400] 
    # Lite kryptiskt; den sparar bara dem hus som har en position 
    # lägre är sista husets position minus 400 
    # (brevlådan är ju 200 m från sista huset)

print "\nAntal platser:", i

Här är ett lösningsexempel i Java. Vi läser in alla hus, sorterar dem, och sedan jobbar vi oss systematiskt framåt genom att placera en brevlådeplats 200 meter framför ett hus om det inte redan finns någon brevlådeplats inom 200 meter från huset.

import java.util.*;

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

		System.out.print("Antal hus: ");
		int antal = scan.nextInt();

		//Våra hus.
		int [] hus = new int [antal];

		//Läser in husen.
		for(int i = 0; i<antal; i++)
		{
			System.out.print("Position för hus " + (i+1) + ": ");
			hus[i] = scan.nextInt();
		}

		//Sorterar husen, så att huset närmast 0 hamnar först i arrayen osv.
		Arrays.sort(hus);

		//Hur många brevlådeplatser vi placerat ut.
		int min = 1;

		//Senaste brevlådeplatsen vi placerat ut.
		//Vi placerar den första 200 meter ifrån det första huset.
		int mailbox = hus[0] + 200;

		//Går igenom alla hus.
		for(int i = 1; i<antal; i++)
		{
			//Avståndet mellan huset och senaste utplacerade brevlådeplats.
			int distance = Math.abs(hus[i]-mailbox);

			//Om avståndet är större än 200 meter...
			if(distance>200)
			{
				//...så placerar vi nästa brevlådeplats 200 meter ifrån detta hus.
				mailbox = hus[i] + 200;

				//Ökar antalet brevlådeplatser.
				min++;
			}
		}

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

Lösning i Haskell.

-- Brevlådeplacering
module Main where
import IO
import Data.List

main = do {
	putStr "Antal hus ? ";
	antal <- getLine;
	
	hus <- readHus 1 (read antal);
	
	putStrLn $ "Antal platser: " ++ (show $ placera $ sort hus)
}

readHus :: Int -> Int -> IO [Int]
readHus _ 0 = return []
readHus n to = do {
		putStr ("Position for hus " ++ (show n) ++ " ? ");
		hus <- getLine;
		
		rest <- readHus (n+1) (to-1);
		
		return $ (read hus):rest
}

placera :: [Int] -> Int
placera [] = 0
placera hus = 1 + (placera [x | x <- hus, (head hus)+400<x])