Tävlingsprogrammering/Uppgifter/Ekokörning
Ekokörning
De flesta bilister vet att nyckeln till låg bränsleförbrukning är att köra med jämn och låg fart. Tyvärr tillåter ofta inte vägen att man kör helt jämnt, det finns dels skiftande hastighetsbegränsningar, dels platser där farten begränsas naturligt, t.ex. när man svänger. Dessutom har man ofta någon tid att passa, så man kan inte köra hur långsamt som helst.
Skriv ett program som, givet sådana begränsningar, beräknar den minimala bränsleförbrukningen för en viss vägsträcka.
Vägsträckan består av N hundrametersintervall (1 ≤ N ≤ 100). Vi antar att man vid start- och slutpunkten för varje intervall har hastigheter v1 respektive v2 km/h som måste vara jämnt delbara med 10. Vid varje sådan punkt är den maximala hastigheten begränsad till ett givet värde. Vidare antar vi[1] att bränsleförbrukningen (i milliliter) för intervallet är
där
som vi antar är medelhastigheten för intervallet (för att slippa bry oss om exakt hur acceleration och bromsning sker inom intervallet). Tiden i sekunder det tar att köra intervallet blir då förstås
Den totala tiden för hela sträckan får inte överskrida T sekunder (1 ≤ T ≤ 5000). Vid sträckans början har du hastigheten 0. Vi bortser från begränsningar i bilens förmåga att accelerera och bromsa. Observera att du inte kan hålla hastigheten 0 i ett helt intervall (då kommer du aldrig framåt), däremot kan du vid en viss position komma ner till hastigheten 0.
- ↑ Detta är en grov modell men för den intresserade följer här en motivering: Den första termen beror på att många krafter (luftmotstånd, friktion m.m.) är ungefär proportionella mot bilens hastighet. Konstantens storlek är naturligtvis beroende av bilmodell etc. men 0.6 liter/mil vid 100 km/h är en rimlig siffra. I verkligheten spelar också växlarnas lägen och motorns verkningsgrad vid olika varv in, så förhållandet är sublinjärt. Den andra termen är ökningen av bilens rörelseenergi vid acceleration, beräknat för vikten 1660 kg och energivärdet 32 MJ/liter för bensin. I idealfallet får man tillbaka hela denna rörelseenergi som minskad förbrukning när man bromsar (därför har vi samma formel även för v2 < v1), men man kan naturligtvis aldrig få negativ förbrukning.
Indata
Första raden i filen eko.dat innehåller talen N och T, separerade med blanksteg. Därefter följer en rad med N blankstegsseparerade tal som anger maxhastigheten i slutet av varje intervall (maxhastigheten för startpunkten är irrelevant eftersom vi har hastigheten 0). Talen är mellan 0 och 120 (inklusive) och jämnt delbara med 10. Det första talet är aldrig 0 och två på varandra följande tal är aldrig 0.
Utdata
Programmet ska skriva ut den minimala bränsleförbrukningen i milliliter, d.v.s. summan av f för de N intervallen när du kör optimalt och ändå kommer fram senast vid tiden T sekunder (för givna testdata är det alltid möjligt att komma fram i tid). Svaret ska vara exakt angivet (men formatet spelar ingen roll).
Exempel 1
2 40 70 70
Svar
3.2
Förklaring: På första delsträckan accelererar du till 30 km/h och förbrukar 2.7 ml. På andra delsträckan bromsar du till 20 km/h och förbrukar 0.5 ml. Den totala tiden är 38.4 sekunder.
Exempel 2
8 61 50 80 80 80 50 50 100 0
Svar
33
Förklaring: På första “landsvägen” är det värt att accelerera upp till maxhastigheten, men efter 50-sträckan är det inte lönt. Din hastighet efter varje intervall är: 50, 80, 80, 70, 50, 50, 60, 0
Exempel 3
15 218 120 0 120 0 10 10 10 50 50 60 70 80 90 90 90
Svar
104.6
Lösning[redigera]
Det första man bör lägga märke till är att en milliliterförbrukning alltid kommer att ha max en decimal. Dvs. om vi multiplicerar den med 10 får vi alltid ett heltal. Nu kan vi helt enkelt applicera dynamisk programmering. För varje delsträcka tänker vi oss alla kombinationer av start- och sluthastigheter, samt den bränsleförbrukningen vi hade hittills på den startpunkten av den delsträckan. Vi sparar den minimala tiden vi hittills kan ha förbrukat när vi kört klart delsträckan för varje sådan kombination. När vi är klara så kollar vi helt enkelt vilken den minsta förbrukning som hade en giltig tid.
#include <cstdio>
#include <cstdlib>
#define MAX_ML 16321
#define INF 6000
int N;
double T;
int V[100];
//Returnerar egentligen antal milliliter multiplicerat med 10
int milliliter(int v1, int v2){
int medel = (v1+v2)/2;
int ml = medel/5*3 + (v2*v2-v1*v1)/50;
if (ml < 0) ml = 0;
return ml;
}
double tid(int v1, int v2){
return 720.0/(v1+v2);
}
double dp[2][13][MAX_ML+1];
int main(){
scanf("%d %lf", &N, &T);
for(int i=0; i<N; i++){
scanf("%d", &V[i]);
}
for(int j=0; j<=12; j++) for(int k=0; k<=MAX_ML; k++)
dp[1][j][k] = INF;
for(int j=10; j<=V[0]; j+=10){
dp[1][j/10][milliliter(0, j)] = tid(0, j);
}
for(int i=1; i<N; i++){
for(int j=0; j<=12; j++) for(int k=0; k<=MAX_ML; k++)
dp[!(i%2)][j][k] = INF;
for(int j=V[i] == 0 ? 10 : 0; j<=V[i-1]; j+=10){
for(int k=j == 0 ? 10 : 0; k<=V[i]; k+=10){
for(int m=0; m<=MAX_ML; m++){
int ml = m + milliliter(j, k);
double old_time = dp[i%2][j/10][m];
double t = old_time + tid(j, k);
if (t <= T && dp[!(i%2)][k/10][ml] > t){
dp[!(i%2)][k/10][ml] = t;
}
}
}
}
}
for(int i=0; i<=MAX_ML; i++) for(int j=0; j<=120; j+=10) if (dp[N%2][j/10][i] < INF){
printf("%.1lf\n", i/10.0);
exit(0);
}
}
Ovanstående kod kanske kör tillräckligt snabbt i C++, men kopierar man koden och skriver motsvarande i Java, så kommer den att ta ca 20 sek (AMD Turion 2GHz Dual Core) för testfall 5. Så då gäller det att analysera vad som tar tid. Jo det som tar mest tid är givetvis den trippelt nästlade for-loopen som innehåller åtminstone två divisioner samt anrop till förbruknings- respektive tids-funktionen (som i sin tur innehåller multiplikationer och divisioner). Så vad kan man göra? Jo till en början kan man införa en if-sats som går vidare till nästa varv i for-loopen om den nådda positionen inte har nåtts (eller nåtts med för stor tid); detta fick faktiskt ned exekveringstiden till ca 10 sek.
Nästa steg är att försöka få bort alla divisioner (divisioner tar tid för en processor att utföra). Detta kan man göra genom att loopa mellan 0-12 istället för 0,10...120 och istället multiplicera variablerna med 10 när man skickar dem till funktionerna (multiplikation är att föredra framför division) samtidigt som man då slipper dela med 10 när man indexerar matrisen. Tiden ligger nu på ca 5-6 sek. Vad kan vi mer göra? Jo vi kan faktiskt anpassa förbruknings- och tids-funktionen efter det faktum att hastigheterna är delade med 10 (och då slippa multiplicera dem med 10 när vi skickar dem till funktionerna). Tidsfunktionen är från början 720/(v1+v2), men om vi har delat både v1 och v2 med 10, så kommer ju 72/(v1+v2) ge samma resultat. Gör vi motsvarande anpassningar för förbrukningsfunktionen kan vi otroligt nog konstatera att vi har lyckats få bort alla divisioner i den funktionen! Programmet exekverar nu på ca 2,5 sek.
Vanligtvis brukar man inte behöva tänka på de små detaljerna när man programmerar i ett högnivåspråk som Java, men om de görs ofta kan det vara nödvändigt och faktiskt ge märkbart resultat. Observera att vi faktiskt inte ändrat på algoritmen, utan bara fått ner antalet instruktioner och antalet divisioner. Oerhört underhållande och lärorikt problem för en Java-programmerare.
Nedanstående lösning använder sig inte av det fyndiga tricket att alternera mellan två "rader" i den tredimensionella vektorn, utan använder sig av två separata matriser för tydlighet och förståelse för läsaren.
import java.util.*;
import java.io.*;
public class EkoKorning
{
//v1 och v2 är egentligen multipler av 10.
//Delas båda med 10 måste 720/10 -> 72.
public static float t(int v1, int v2)
{
return 72f/(v1+v2);
}
//v1 och v2 ska egentligen båda delas med 2 och 5.
//Men eftersom de båda delats med 10 behövs inte det.
//Delas v1 och v2 med 10 minskas (v2*v2-v1*v1) med en faktor 100,
// varför /50 blir *2.
public static int f(int v1, int v2)
{
int ml = (v1+v2)*3 + (v2*v2 - v1*v1)*2;
return ml<0 ? 0 : ml;
}
//Orka fånga exceptions. Vi är lata och säkra på vår sak.
public static void main(String [] klein) throws FileNotFoundException
{
//long tid = System.currentTimeMillis();
//Vi ska läsa av filen eko.dat i mappen/katalogen data.
Scanner scan = new Scanner(new File("data\\eko.dat"));
//Antal delsträckor och maxtid.
final int N = scan.nextInt();
final int T = scan.nextInt();
//Läser in hastigheterna och delar dem med 10.
int [] str = new int [N];
for(int i = 0; i<N; i++) str[i] = scan.nextInt()/10;
//Maximal förbrukning och löjligt stor tid.
final int maxMl = 16321, inf = 6000;
//Minsta tid för en viss hastighet/10 och förbrukning.
// [hastighet/10][förbrukning]
float [][] prev = new float [13][maxMl+1]; //Föregående delsträcka.
float [][] next = new float [13][maxMl+1]; //Nästa delsträcka.
//Sätter en ouppnåligt stor tid för alla tillstånd.
//Beräknar tid för "de olika möjliga hastigheterna och förbrukning"
// för den första delsträckan.
for(int i = 0; i<13; i++) Arrays.fill(next[i], inf);
for(int i = 1; i<=str[0]; i++) next[i][f(0,i)] = t(0,i);
//Går igenom de övriga delsträckorna.
for(int i = 1; i<N; i++)
{
//Kopierar över de tider vi fann i föregående loop-varv
// till prev-vektorn, och "nollställer" next-vektorn.
for(int j = 0; j<13; j++)
{
System.arraycopy(next[j], 0, prev[j], 0, maxMl+1);
Arrays.fill(next[j], inf);
}
//j: Går igenom alla de möjliga hastigheter för föregående delsträcka.
//Är max för nuvarande 0 kan inte föregående vara det, eller tvärtom.
//k: Går igenom alla möjliga hastigheter för nuvarande sträcka.
//m: Går igenom alla möjliga förbrukningar.
for(int j = str[i]==0 ? 1 : 0; j<=str[i-1]; j++)
for(int k = j==0 ? 1 : 0; k<=str[i]; k++)
for(int m = 0; m<=maxMl; m++)
{
//Har vi inte nått föregående tillstånd är det onödigt att
// exekvera nedanstående kod. (Vi sparar tid.)
if(prev[j][m]==inf) continue;
//Ny förbrukning om man går från hastighet j*10 till k*10.
int ml = m + f(j,k);
//Ny total tid som det tagit. Föregående tid + tid delsträckan tar.
float t = prev[j][m] + t(j,k);
//Är tiden godkänd och den bästa hittills sparas den.
if(t<=T && t<next[k][ml]) next[k][ml] = t;
}
}
//Letar reda på den minsta förbrukningen som har en godkänd tid.
loop:for(int i = 0; i<=maxMl; i++)
for(int j = 0; j<=12; j++)
if(next[j][i]<inf)
{
System.out.println("Svar: " + (i/10f));
break loop;
}
//System.out.println("Tid: " + (System.currentTimeMillis()-tid));
}
}
En kul sak är att när jag (som skrev C++-lösningen) testar att lägga in optimeringarna som föreslås ovan går programmet inte alls snabbare (i C++). Förmodligen är gcc så bra på att optimera att det inte spelar roll exakt vad man skriver; den producerar snabbaste koden ändå. Dock så gör den där extra if-satsen man kan lägga in i den tightaste loopen programmet dubbelt så segt. Det är faktiskt också bättre att ta bort den även i java-lösningen (sparade 10% körtid), i alla fall på min dator. Av nån anledning blev det faktiskt också snabbare i java att ha två stycken arrayer (prev och next) som man kopierar mellan, istället för att växla med i%2 som jag gör i C++-versionen... Hur som helst blev java-lösningen ändå aldrig snabbare än 4 ggr så seg som C++-versionen.
Processorer kan uppenbarligen skilja sig åt. Men här är en ännu mer optimerad Java-version som klarar det värsta testfallet under 1 sek. Vad man kan göra är att byta plats på k- och m-loopen och sedan flytta ut if-satsen utanför k-loopen. Löjliga små optimeringar i funktionen f(v1,v2) har också gjorts, vilka förmodligen är roten till all ondska enligt Donald Knuth, men ack så roliga! (Vi lyckas undvika multiplikation med 3. :P)
import java.util.*;
import java.io.*;
public class EkoKorning
{
//v1 och v2 är egentligen multipler av 10.
//Delas båda med 10 måste 720/10 -> 72.
public static float t(int v1, int v2)
{
return 72f/(v1+v2);
}
//v1 och v2 ska egentligen båda delas med 2 och 5.
//Men eftersom de båda delats med 10 behövs inte det.
//Delas v1 och v2 med 10 minskas (v2*v2-v1*v1) med en faktor 100,
// varför /50 blir *2.
public static int f(int v1, int v2)
{
final int v = v1+v2;
int ml = (v2*v2 - v1*v1 + v << 1) + v;
return ml<0 ? 0 : ml;
}
//Orka fånga exceptions. Vi är lata och säkra på vår sak.
public static void main(String [] klein) throws FileNotFoundException
{
//long tid = System.currentTimeMillis();
//Vi ska läsa av filen eko.dat.
Scanner scan = new Scanner(new File("eko.dat"));
//Antal delsträckor och maxtid.
final int N = scan.nextInt();
final int T = scan.nextInt();
//Läser in hastigheterna och delar dem med 10.
final int [] str = new int [N];
for(int i = 0; i<N; i++) str[i] = scan.nextInt()/10;
//Minsta tid för en viss hastighet/10 och förbrukning.
// [hastighet/10][förbrukning]
float [][] prev = new float [13][16321+1]; //Föregående delsträcka.
float [][] next = new float [13][16321+1]; //Nästa delsträcka.
//Beräknar tid för "de olika möjliga hastigheterna och förbrukning"
// för den första delsträckan.
for(int i = 1; i<=str[0]; i++) next[i][f(0,i)] = t(0,i);
int max = f(0,str[0]);
//Går igenom de övriga delsträckorna.
for(int i = 1; i<N; i++)
{
//Kopierar över de tider vi fann i föregående loop-varv
// till prev-vektorn, och "nollställer" next-vektorn.
for(int j = 0; j<13; j++)
{
float [] tmp = prev[j];
prev[j] = next[j];
Arrays.fill(next[j] = tmp, 5, max+1, 0);
}
//j: Går igenom alla de möjliga hastigheter för föregående delsträcka.
//Är max för nuvarande 0 kan inte föregående vara det, eller tvärtom.
//k: Går igenom alla möjliga hastigheter för nuvarande sträcka.
//m: Går igenom alla möjliga förbrukningar.
for(int j = str[i]==0 ? 1 : 0; j<=str[i-1]; j++)
for(int m = 5; m<=max; m++)
{
//Har vi inte nått föregående tillstånd är det onödigt att
// exekvera nedanstående kod. (Vi sparar tid.)
if(prev[j][m]>0)
for(int k = j==0 ? 1 : 0; k<=str[i]; k++)
{
//Ny total tid som det tagit. Föregående tid + tid delsträckan tar.
float t = prev[j][m] + t(j,k);
if(t>T) continue;
//Ny förbrukning om man går från hastighet j*10 till k*10.
int ml = m + f(j,k);
//Är tiden godkänd och den bästa hittills sparas den.
if(next[k][ml]==0 || t<next[k][ml]) next[k][ml] = t;
}
}
max += f(str[i-1]==0 ? 0 : 1, str[i]);
}
//Letar reda på den minsta förbrukningen som har en godkänd tid.
loop:for(int i = 0; ; i++)
for(int j = 0; j<=str[N-1]; j++)
if(next[j][i]>0)
{
System.out.println("Svar: " + (i/10f));
break loop;
}
//System.out.println("Tid: " + (System.currentTimeMillis()-tid));
}
}