Tävlingsprogrammering/Uppgifter/Terrängloppet
Terrängloppet
Henning ska springa ett terränglopp där han vill minimera sin tid. Hans fysiska förmåga
har (efter mycket datorspelande) diskretiserats så att han har fem “växlar” att välja
mellan men ingen möjlighet att kontinuerligt välja ansträngningsnivå. Vidare är hans
“energi” också diskretiserad till ett heltal mellan 0 (helt utpumpad) och K (full-laddad).
På varje hundrameterssträcka ändras energin med ett visst belopp D, som beror på vilken
växel Henning springer på. För de fem växlarna är D = −3, −2, −1, 0 och +1. Med
andra ord blir han tröttare på de tre första växlarna (D < 0), ändrar inte energi på den
fjärde växeln, samt återhämtar sig något på den sista växeln (D > 0). Han kan naturligtvis
inte välja en växel som ger negativ energi efter sträckan. Vidare kan han aldrig
få högre energi än K; skulle han välja återhämtningsväxeln när han redan har energin
K så förblir energin oförändrad.
Henning har detaljtränat på banan där loppet ska gå. Han har lyckats göra upp en tabell för hur snabbt han kan springa varje hundrameterssträcka av loppet på var och en av sina växlar, med hänsyn tagen till lutning, underlag o.s.v. Skriv ett program som beräknar den minimala tiden Henning kan springa hela loppet på om han vid loppets början är full-laddad, d.v.s. har energin K.
På första raden i filen loppet.dat står två heltal: antalet hundrameterssträckor (1 ≤ N ≤ 1000) samt maxenergin (1 ≤ K ≤ 100). Därefter följer N rader som beskriver hundrameterssträckorna i ordning från start till mål. Varje rad innehåller fem heltal separerade med blanksteg, tiden i sekunder det tar att springa sträckan på var och en av växlarna. Det första talet gäller växeln med D = −3, det andra D = −2 o.s.v. Tiden för en växel med högre D är aldrig lägre än den för ett lägre D och alla tiderna ligger mellan 10 och 75 sekunder. Programmet ska skriva ut den minimala totaltiden (i sekunder) för hela loppet.
Exempel: Filen loppet.dat med innehållet
8 10 22 25 26 28 30 22 24 26 27 28 25 26 29 35 42 25 27 30 38 44 22 24 26 28 31 20 23 26 28 30 19 21 24 26 30 23 25 27 30 30
ska ge svaret
Minsta totaltid: 203
Kommentar: Den optimala taktiken har D-värdena -1, +1, -2, -2, 0, -3, -2 och -1.
Lösning
[redigera]I princip måste vi testa alla kombinationer av växlar; vi kan inte på förhand veta vilken som är den bästa taktiken. Antalet kombinationer kan dock bli 51000 så att loopa igenom alla kan ta sin tid. Lyckligtvis kan man utnyttja det faktum att vid en given position i loppet spelar det ingen roll exakt vilka växlar Henning har sprungit varje sträcka på innan. Det enda som spelar roll är hur mycket energi han har kvar och hur lång tid loppet har tagit hittills. Därför kan man helt enkelt gå igenom loppet sträcka för sträcka och spara, för varje kvarvarande energi, den minimala tiden han kan ha så långt i loppet. För varje sträcka testar man var och en av de fem växlarna på var och en av de K energinivåerna han kan ha före sträckan, och sparar den bästa tiden han kan ha på varje energinivå efter sträckan. Antalet operationer blir då ungefär 5*N*K, d.v.s. bara maximalt 500000, vilket gör att programmet går blixtsnabbt. Denna teknik kallas dynamisk programmering och är mycket användbar i såväl tävlingsprogrammering som applikationer inom t.ex. bioinformatik.
Upplysningen om att tiden för en växel med högre D är aldrig lägre än den för ett lägre D förenklar programmet ytterligare. Det kan då aldrig vara värt att ta en växel som ger högre energi än K, och det kan aldrig vara värt att ha energi kvar i slutet av loppet.
Exempellösning i C:
#include <stdio.h>
int main() {
int t[101],nyt[101],sec[5],N,K,i,j,k;
FILE *fil=fopen("loppet.dat", "rt");
fscanf(fil, "%d %d", &N,&K);
for(k=0;k<=K;k++) t[k]=0; //Tiden är från början 0 oavsett energin (vi kanske inte "hinner" göra åt hela energin K)
for(i=0;i<N;i++) { //Loopa igenom sträckorna
for(j=-3;j<=1;j++) fscanf(fil, "%d", &sec[j+3]);
for(k=0;k<=K;k++) nyt[k]=1000000000; //Initiera den nya tiden med ett oändligt högt värde
for(k=0;k<=K;k++) for(j=-3;j<=1;j++) //För varje energi och varje växel
if(k+j>=0 && k+j<=K) { //Om den nya energin ligger mellan 0 och K...
if(t[k]+sec[j+3] < nyt[k+j]) nyt[k+j] = t[k]+sec[j+3]; //... så kolla om tiden är bättre än den hittills bästa
}
for(k=0;k<=K;k++) t[k]=nyt[k]; //Flytta över de nya tiderna till tids-vektorn
}
printf("Minsta totaltid: %d\n", t[0]); //Skriv ut tiden för energin 0
return 0;
}
Här är en lösning i Java, som visserligen inte är lika snabb som ovanstående, men å andra sidan kanske en aning lättare att förstå sig på.
import java.util.*;
import java.io.*;
public class TLoppet
{
//Tabell där vi lagrar de olika tiderna för en sträcka.
static int [][] tabell;
//Matris för dynamisk programmering.
//Vi kommer skriva in en viss tid för en viss mängd energi
// en viss runda.
static int [][] visited;
//Hur många 100-meters sträckor som förekommer.
static int antal;
//Vår maxenergi.
static int energi;
//Vår minimum-tid.
static int min = Integer.MAX_VALUE;
//Vår rekursvia metod som testar alla möjligheter och löser problemet.
/*
round: Hur många sträckor á 100 meter vi sprungit.
time: Hur lång tid som har gått.
energy: Hur mycket energi vi har kvar.
*/
public static void rek(int round, int time, int energy)
{
//Onödigt att fortsätta med denna dumma uppsättning växlar.
if(time>=min)
{
return;
}
else if(round==antal) //Annars om vi sprungit klart så är vår tid bäst.
{
min = time;
return;
}
//Om vår tid är bättre än den tidigare bästa för denna runda
// med denna energi, så är den den bästa.
if(time<visited[round][energy]) visited[round][energy] = time;
else return; //Annars är vi inne på fel spår.
//Om vi har mer än 1 i energi...
if(energy>=1)
{
//...så får vi testa att välja -1 i växel.
rek(round+1, time+tabell[round][2], energy-1);
//Om vi har mer än 2...
if(energy>=2)
{
//...så får vi också testa växel -2.
rek(round+1, time+tabell[round][1], energy-2);
//Och om vi har mer än 3 så får vi testa -3.
if(energy>=3) rek(round+1, time+tabell[round][0], energy-3);
}
}
//Växel 0 kan vi alltid testa.
rek(round+1, time+tabell[round][3], energy);
//Och växel +1 bör vi endast testa om vi inte har maxenergi.
if(energy!=energi) rek(round+1, time+tabell[round][4], energy+1);
}
//Orka fånga exceptions. Vi är lata och säkra på vår sak.
public static void main(String [] klein) throws FileNotFoundException
{
//Vi ska läsa av filen loppet.dat i mappen/katalogen data.
Scanner scan = new Scanner(new File("data\\loppet.dat"));
antal = scan.nextInt();
energi = scan.nextInt();
//Skapar vår matris för dynamisk programmering.
visited = new int [antal][energi+1];
//De olika tiderna för en viss sträcka.
tabell = new int [antal][5];
//Läser in varje tid på en sträcka.
for(int i = 0; i<antal; i++)
{
tabell[i][0] = scan.nextInt(); //Växel -3.
tabell[i][1] = scan.nextInt(); // -2
tabell[i][2] = scan.nextInt(); // -1
tabell[i][3] = scan.nextInt(); // 0
tabell[i][4] = scan.nextInt(); // +1
//Markerar varje energi-position för en runda med en sinnesjukt hög tid.
for(int j = 0; j<=energi; j++) visited[i][j] = Integer.MAX_VALUE;
}
//Från början har vi inte sprungit någon runda, ingen tid har gått
// och vi är fyllda med energi.
rek(0, 0, energi);
//Skriver ut svaret.
System.out.println("Mista totaltid: " + min);
}
}
Lösning i Haskell, som går att optimera, men det behövs inte för att klara tidsgränsen. (T.ex. skulle man kunna göra någon snajsig form av (zipWith min) istället för att hålla på och sortera och gruppera, då sublistorna för respektive växel kommer att vara sorterade.)
-- Terrängloppet
module Main where
import IO
import Data.List
lopp e = (e,0):(lopp $ e+1)
myGroup = groupBy (\x y -> (fst x) == (fst y) )
main = do {
ih <- openFile "loppet.dat" ReadMode;
content <- hGetContents ih;
rader <- return $ map ((map read).words) $ lines content;
maxE <- return $ (head rader) !! 1;
start <- return $ take (maxE + 1) (lopp 0);
putStrLn $ "Minsta totaltid: " ++ (show $ spring (tail rader) start);
hClose(ih)
}
spring :: [[Int]] -> [(Int, Int)] -> Int
spring [] (h:t) = snd h
spring ([g0,g1,g2,g3,g4]:t) et = spring t (map head $ (myGroup.sort) (v3++v2++v1++v0++vp1))
where
v3 = drop 3 $ map (\(a,b) -> (a-3, g0 + b) ) et
v2 = drop 2 $ map (\(a,b) -> (a-2, g1 + b) ) et
v1 = tail $ map (\(a,b) -> (a-1, g2 + b) ) et
v0 = map (\(a,b) -> (a, g3 + b) ) et
vp1 = init $ map (\(a,b) -> (a+1, g4 + b) ) et