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:
Í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.
- 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
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.Kimenet
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:A hátralévő sorok tartalma:
- 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 számadatok mindegyike pozitív. A benzinkutak kiindulási ponttól mért távolságuk szerint nemcsökkenően vannak elrendezve. Egyik kút sincs a célállomáson túl. Mindig van elég útmenti benzinkút a célbajutáshoz.
- Az első szám a benzinkút starttól mért távolsága
- A második a benzin gallononkénti ára.
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 11.9 27.4 14.98 6 102.0 99.9 220.0 132.9 256.3 147.9 275.0 102.9 277.6 112.9 381.8 100.9 516.3 15.7 22.1 20.87 3 125.4 125.9 297.9 112.9 345.2 99.9 -1 OUTPUT.TXT Data Set #1 minimum cost = $27.31 Data Set #2 minimum cost = $38.09