| Submit | All submissions | Best solutions | Back to list |
AVDM - Adventure in Moving |
To help you move from Waterloo to the big city, you are considering renting a moving truck. Gas prices being so high these days, you want to know how much the gas for such a beast will set you back.
The truck consumes a full litre of gas for each kilometre it travels. It has a 200 litre gas tank. When you rent the truck in Waterloo, the tank is half full. When you return it in the big city, the tank must be at least half full, or you'll get gouged even more for gas by the rental company. You would like to spend as little as possible on gas, but you don't want to run out along the way.
Input
Input is all integers. The first integer is the distance in kilometres from Waterloo to the big city, at most 10000. Next comes a set of up to 100 gas station specifications, describing all the gas stations along your route, in non-decreasing order by distance. Each specification consists of the distance in kilometres of the gas station from Waterloo, and the price of a litre of gas at the gas station, in tenths of a cent, at most 2000.
Output
Output is the minimum amount of money that you can spend on gas to get you from Waterloo to the big city. If it is not possible to get from Waterloo to the big city subject to the constraints above, print "Impossible".
Example
Input: 500 100 999 150 888 200 777 300 999 400 1009 450 1019 500 1399 Output: 450550
| Added by: | [Retired] Fendy Kosnatha |
| Date: | 2011-03-05 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | UVa |
hide comments
|
2016-03-01 06:38:15 [Rampage] Blue.Mary
As :D mentioned, you must process input until EOF, and process all the given stations one by one (as if they are all BETWEEN waterloo & big city). At last print the result. In other words, you do DP assuming L = +inf, and take L into consideration only when calculating the final result. Last edit: 2016-03-01 06:42:48 |
|
|
2011-03-14 16:43:33 :D
It's not only about out-of-bound constrains. You have to give a wrong solution to those cases to get AC. If you properly take them into account it will be a WA. You will also fail if you'll not process gas station from first to last (but in reverse for example). |
|
|
2011-03-14 15:05:54 Ravi Kiran
I think its a little evil to have cases differing from the given constraints. I have been spending the last 2 hours trying to "guess" the input style. I think as :D says, the problem setter must modify the input data to match above constraints or update the problem statement. RE:I have finally got accepted thanks to sonpascal93 for making it clear.In my AC'ed solution, I read the input till EOF and try to process the fuel stations in the order mentioned(not necessarily ascending distances from Waterloo).Hope it helps. Last edit: 2011-03-16 06:59:14 |
|
|
2011-03-13 22:34:32 :D
There are some issues with the input data. First of all, they are gas stations placed further than big city. I got WA when I tried to take them into account (going further and then back to fill the tank with lower cost). I got AC when I completely ignored it and, what's important, assumed that big city with the proper distance is the last (so there were negative distances during processing). Please correct the test data because now only specific way of processing the input can get AC. Last edit: 2011-03-13 22:41:37 |
|
|
2011-03-08 02:37:32 [Retired] Fendy Kosnatha
@Radhakrishnan : this is a DP problem, maybe this is easier than ROADTRIP |
|
|
2011-03-06 09:15:35 Radhakrishnan Venkataramani
DP/RMQ ? Also what do u think of this problem ROADTRIP ? |
|
|
2012-02-25 10:28:35 A. Muh. Primabudi
@mas fendy, how is the input terminated ? |
RSS