Megoldás

Algoritmus

Ha rájövünk a probléma matematikájára (fizikájára), akkor már nagyon egyszerű az algoritmust elkészíteni. A lényeges észrevételek a következők:
  1. Mivel 0 másodperc alatt tudunk lassulni és gyorsulni, nincs jelentősége annak, hogy milyen sorrendben és felosztásban követik egymást a mozgójárdák, csak annak, hogy melyik sebességűből összesen hány méter van. Tekinthetjük úgy a problémát, mintha mindegyik sebességű járdából pontosan egy lenne, beleértve egy "nulladik" mozgójárdát, azt, ahol alapból nincs semmi.
  2. Az az optimális stratégia, ha mindig a lehető leglassabb járdán futunk, amíg még van rá kapacitásunk. Ezt nem nyilvánvaló bizonyítani, de az ember "érzi, hogy így van". Egy lehetséges bizonyítás a felcserélési érvelést használja. Tekintsünk egy w1 és egy w2 sebességű járdát, és tegyük fel, hogy az elsőn r1 ideig futottunk, s1 ideig gyalogoltunk, a másodikon pedig r2 ideig futottunk és s2 ideig gyalogoltunk. Tegyük fel továbbá, hogy w1 < w2. Ha a futás egy részét "átcsoportosítjuk" a lassabb járdára, vagyis ott r1+ ε ideig futunk, akkor a másik járdára r2 ε idő jut futásra. Továbbá nyilván megváltoznak a gyaloglásra megmaradó s1' és s2' idők.
    Megmutatható némi számolással, hogy rrs1' + s2' < rrss2.
Az algoritmus tehát a következő: sorba rendezzük a járdákat sebességük szerint, és a leglassabbal kezdve mindvégig futunk, amíg van még rá kapacitás. Mivel a járdák maximális száma kicsi, nincs jelentősége, mennyire hatékony rendezési algoritmust használunk.

Kódok

Forrás Bence (java): fobe_repuloter.java
Tegzes Tamás (pascal): tt_airport.pas