Tävlingsprogrammering/Uppgifter/Storken

Storken (PO-onlinekvalet 2008)

En ibis-stork som bor vid Assuan-dammen hundra mil uppåt Nilen tänker hälsa på en kusin i Nildeltat. Han är dock ganska lat så att flyga själv är inget alternativ. Med tanke på den täta båttrafiken på Nilen bestämmer han sig för att lifta med flodbåtarna. Skriv ett program som, givet rutter, avgångstider och hastigheter för alla nedströms gående båtar, beräknar den tidigaste tidpunkten storken kan vara framme hos sin släkting.

Storken är resklar vid tidpunkten 0 timmar och han befinner sig då vid positionen 0 km. Resmålet ligger vid positionen 1000 km. Vi antar att storken utan fördröjning kan förflytta sig i "sidled" över floden, t.ex. från en båt till en annan eller från land till en förbipasserande båt. Däremot vägrar han flyga en enda kilometer längs med floden, så båtar måste användas för hela transporten.

Indata

Första raden innehåller ett heltal n, där 1 ≤ n ≤ 1000: antalet båtar. Därefter följer n rader som vardera beskriver en båt. Varje rad innehåller fyra heltal: startpositionen s, slutpositionen m, avgångstiden t samt hastigheten v, vilka uppfyller 0 ≤ s < m ≤ 2000, 0 ≤ t ≤ 1000 och 1 ≤ v ≤ 50. Positionerna anges i kilometer, avgångstiden i timmar och hastigheten i kilometer per timme. Rutten är planerad så att båten kommer fram till sin slutposition på ett helt klockslag, d.v.s. restiden (m-s)/v är alltid ett heltal.

Utdata

Programmet ska skriva ut en rad med ett heltal: det första hela klockslaget (d.v.s. antalet timmar efter tidpunkten 0) på vilket storken kan vara hos sin kusin. I samtliga testfall kan storken komma fram.

Exempel: Indata

5
250 875 15 25
0 400 5 20
500 600 0 20
50 250 10 40
600 1100 30 15

Exempel: Utdata

57

Exempel: Förklaring

Storken startar sin resa med båt 2 som avgår "klockan 5". Mellan klockan 12 och 13 blir denna båt omkörd av båt 4 och storken flyger över till den. Detta gör att storken hinner fram till position 250 km precis när båt 1 avgår och fågeln kan sedan åka med denna båt till dess slutposition. Där får storken vänta i drygt 8 timmar (på land) innan båt 5 kommer förbi och tar honom till kusinen, dit han anländer strax innan klockan 57.

Lösning

Här gäller det att inse att en s.k. girig (greedy) algoritm, d.v.s. en algoritm som väljer det bästa alternativet för stunden, faktiskt fungerar. Vid varje tidpunkt är det alltid bäst för storken att ha kommit så långt som möjligt, för om det vid någon tidpunkt skulle vara fördelaktigt att befinna sig längre uppströms kan storken helt enkelt flyga i land och vänta på att den "bättre" resrutten kommer ifatt honom (alltså är den inte bättre).

Så programmet kan ha formen av en simulering där man hela tiden låter storken välja båtar som ligger så långt fram som möjligt. Ett möjligt sätt att göra detta skulle vara att räkna ut alla exakta omkörningstidpunkter och sedan loopa sig fram i en sorterad lista av "händelser", d.v.s. avgångar, ankomster och omkörningar (även av redan anlända båtar), och hela tiden välja den snabbaste båten.

Det finns dock ett betydligt enklare sätt som möjliggörs av att båtarna avgår och anländer på hela timmar. Vi behöver inte ens veta när omkörningarna sker. Om storken befinner sig vid position p vid tiden t, så ska den alltid, bland de båtar som är igång och befann sig uppströms om p vid tiden t, välja den båt som vid tiden t+1 har kommit längst nedtröms om p, och åka med denna båt en hel timme. Om det inte finns någon sådan båt ska storken helt enkelt stanna där den är.

Att storken aldrig behöver hoppa av en båt mellan de hela klockslagen kan verka paradoxalt, men det klarnar när man tänker efter lite. Antag att storken sitter på en båt som blir omkörd t.ex. klockan 14.15 av en snabbare båt. Istället för att flyga över till den andra båten precis när omkörningen sker kan storken lika gärna flyga över till land klockan 14.00 (vid x km) och vänta där tills den snabbare båten kommer förbi. Vilket storken sedan tycker är bekvämast kan vi ju lämna åt den själv att bestämma, det viktiga är att det inte blir någon skillnad i slutänden. Man skulle kunna invända att den snabba båten kanske startar sin resa längre ner än punkten x, men då skulle den ju befinna sig nedströms om den långsamma båten och därför försvinna iväg utan att stöta på denna.

Lösningsexempel i C

#include <stdio.h>

int main(){
  int i,N,start[10000],slut[10000],avg[10000],v[10000],ank[10000],t,p,max;
  scanf("%d", &N);
  for(i=0;i<N;i++) {
    scanf("%d %d %d %d",&start[i],&slut[i],&avg[i],&v[i]);
    ank[i]=avg[i]+(slut[i]-start[i])/v[i];   //Båtens ankomsttid
  }
  p=0;     //Storkens aktuella position
  t=0;    //Den aktuella tidpunkten
  while(p<1000) {
    max=p;                             //Storken vill ju i sämsta fall stanna kvar på samma plats
    for(i=0;i<N;i++) if(avg[i]<=t && ank[i]>t) {                                     //Av alla båtar som är igång mellan t och t+1...
        if((start[i]+(t-avg[i])*v[i] <= p) && (start[i]+(t+1-avg[i])*v[i] >max))   //...och som vid tiden t är uppströms om storken... 
          max=start[i]+(t+1-avg[i])*v[i];                                            //...välj den som vid tiden t+1 har kommit längst.
      }
  p=max;  //Flytta storken till ny position
  t++;   //Tiden går...
  }
  printf("%d\n", t);
  return 0;
}