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
redigeraHur 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])