Adventures in Moving - Part IV
InterviewTime limit1sMemory limit128 MB
Given a route with up to 100 gas stations, each with a price per litre, find the cheapest way to fuel a truck with a 200-litre tank that starts and ends half full.
- Level
Medium6 of 10
- Topics
- Greedy, Dynamic programming, Array, Simulation
- Solved
- No attempts yet
Problem
To help you move from Waterloo to the big city, you are thinking about renting a moving truck. With gas prices so high these days, you want to know in advance how much fuel for such a beast will cost you.
The truck burns exactly one litre of gas for every kilometre it travels. Its tank holds 200 litres. When you pick the truck up in Waterloo the tank is half full, that is 100 litres. When you return it in the big city the tank must again be at least half full (100 litres), otherwise the rental company charges you a much steeper price for gas. You want to spend as little as possible on fuel, but you must never run out along the way.
Input
The input consists entirely of integers. The first integer is the distance in kilometres from Waterloo to the big city, at most 10000. It is followed by the descriptions of up to 100 gas stations along your route, given in non-decreasing order of distance (equal distances are allowed). Each station is described by two integers: its distance in kilometres from Waterloo, and the price of one litre of gas at that station. The price is measured in tenths of a cent and is at most 2000.
Output
Output the minimum amount of money you can spend on gas to get from Waterloo to the big city. Because prices are given in tenths of a cent, the answer is an integer in the same unit. If it is impossible to reach the big city without running out of gas along the way, output "Impossible".