Want to try solving this problem? You can submit your code online if you log in or register.
Time Limit: 0.02 seconds
Memory Limit: 30 Mb
It's fashion week, and you are trying on the latest designer belts from Paris. Unfortunately none of the belts fit you, which can mean only one thing. You need more exercise.
You decide the best time to exercise is during your tram ride home. The tram runs in a straight line from school to home, and there are several stops on this line. You can get some exercise by hopping off the tram at some stop, walking to another stop further down the line, and then hopping onto the next tram that comes by. You can do this as many times as you like (tram, walk, tram, walk and so on). You may choose to start the journey walking if you wish, and you may choose to hop off a tram at some point and walk the rest of the way home.
Trams run every t minutes, with the first tram leaving school precisely when you begin your journey. Trams move at a fixed speed, and you walk at a slower fixed speed. You may only walk forwards — you may not walk backwards or walk around in circles. If you are walking from stop a to stop b and catching the next tram, you simply wait at stop b and listen to your mp3 player until the next tram comes along. If you arrive at stop b at precisely the same moment as a tram comes past, you may hop on board.
After poring through a handful of health magazines, you decide that you need to walk at least k metres during your travels home. Your task is to find the shortest possible travel time from start to finish that meets this requirement.
All times below are measured in milliseconds, and all distances are measured in metres.
Consider the tram line illustrated below. It begins with the school on the left hand side, after which come s=6 tram stops. Distances between consecutive stops are marked on the diagram, and your house is at the very last stop.
Suppose that the council is extremely efficient, and that trams run every 30 seconds, i.e., every t=30,000 milliseconds. Trams take mt=1 millisecond to move one metre, and you take a brisk mw=100 milliseconds to walk one metre. Your fitness regime requires you to walk at least k=870 metres during your journey.
An optimal strategy for getting home is as follows.
Action | Stops | Distance | Time |
---|---|---|---|
Tram | School–1 | 450m | 450ms |
Walk | 1–2 | 300m | 30,000ms |
Wait for tram | 2 | 300ms | |
Tram | 2–3 | 450m | 450ms |
Walk | 3–5 | 600m | 60,000ms |
Wait for tram | 5 | 600ms | |
Tram | 5–6 | 450m | 450ms |
Total | 92,250ms |
Your total walking distance according to this plan is 900m, which is enough since it is more than the required k=870m. The total travel time is 92,250 milliseconds.
Your program must read from standard input. The first line will contain the single integer t, giving the time between each tram and the next. The second line will contain the two integers mt and mw separated by a single space, giving the time it takes a tram to move one metre and the time it takes you to walk one metre. The third line will contain the single integer k, giving the minimum distance that you need to walk.
The fourth line of input will contain the single integer s, giving the total number of tram stops (excluding the school where the journey begins). Following this will be s lines, giving the positions of the individual stops in consecutive order from school to home. The ith of these lines will contain the integer di, giving the distance from the school to the ith stop. Your house is at the last of these stops.
Once more, all times are measured in milliseconds and all distances are measured in metres.
Your program must write a single line to standard output. This line must contain a single integer giving the shortest time possible for the entire journey, measured in milliseconds.
30000 1 100 870 6 450 750 1200 1740 1800 2250
92250
The score for each input scenario will be 100% if the correct answer is output, or 0% otherwise.
Privacy
statement
© Australian Mathematics Trust 2001-2021
Page generated: 1 December 2021, 10:52am AEDT