Egy amerikai utazási irodát néha felkérnek arra, becsülje meg a minimális autós utazási költséget egyik várostól a másikig. Az utazási iroda nyilvántartja a leggyakrabban használt utak mentén található benzinkutak helyét a kútnál alkalmazott gallononkénti árakat.
A költségbecslés egyszerűsítése érdekében az iroda a következő hozzávetőleges számítást alkalmazta a sofőrök számára:
ˇ a sofőr sohasem áll meg egy benzinkútnál, amikor a kocsi tankjában több benzin van a tank felénél, kivéve, ha ez nem elegendő a következő kútig vagy a végcélig.
ˇ a sofőr mindig teletölti a tankot
ˇ a sofőr minden benzinkútnál 2.0 dollárt költ el étkezésre és más apróságokra
ˇ a sofőrnek nincs szüksége több üzemanyagra a következő kút vagy a célváros eléréséhez, mint a tank mérete, azaz nincs szükség pótüzemanyagra
ˇ a sofőr mindig teli tankkal indul útnak
ˇ a megálláskor fizetett összeget mindig centre kerekítik
Írj programot, amely meghatározza az út megtételéhez szükséges minimális költséget, beleértve a benzin mellett az egyéb költségeket is.
Bemenet
A bemenet különböző utazások adatsorozatait tartalmazza. Minden adatsorozat néhány sornyi információt tartalmaz. Az első két sor a kiindulási helyről és a célról tartalmaz információt. A hátralévő sorok az útmenti benzinkutak adatait tartalmazzák, soronként egyet-egyet. Az alábbiakban a bemenet pontos formáját írjuk le.
1. sor: Egyetlen valós számot, a start-cél távolságot adja meg.
2. sor: Három valós és egy egész számot tartalmaz:
ˇ Az első valós szám az autó tankjának méretét adja meg.
ˇ A második valós szám megadja, hogy hány mérföld utat képes 1 gallon üzemanyaggal megtenni.
ˇ A harmadik valós szám leírja, hogy a kiindulási helyen mennyibe került az autó teletankolása
ˇ Az egész szám az útmenti töltőállomások számát adja meg.
A hátralévő sorok tartalma:
ˇ Az első szám a benzinkút starttól mért távolsága
ˇ A második a benzin gallononkénti ára.
A számadatok mindegyike pozitív. A benzinkutak kiindulási ponttól mért távolságuk szerint nem csökkenően vannak elrendezve. Egyik kút sincs a célállomáson túl. Mindig van elég útmenti benzinkút a célba jutáshoz.
Kimenet
Minden bemeneti adatsorozathoz az adatsorozat számát és a minimális költséget kell kiíratni, amelybe beleértendő az induláskori teletankolás és az ennivaló ára is.
|
INPUT.TXT |
|
475.6
|
|
OUTPUT |
|
Data Set #1
|
(ACM döntő 1993)