 |
Contest 8: Cheap Way
Difficulty: Advanced |
Problem:
The country of Hill-land has N towns (5<=N<=1000), labeled with the numbers from 1..N, and M paths (ways), connecting pairs of towns (N<=M<=100 000). For every path (between two towns) is known its length - integer <= 1000. The paths in Hill-land are very strange. For every of them, when you leave the town (i.e. when the path starts), you start ascending, and this- up to the middle of the path, where is a hill. After this middle, you continue but to descent, down to the end of the path (i.e. to the entrance of the other town).
That's why, the local drivers are used to drive this way: when a driver reaches the top of the hill (i.e. the middle of the path), then he turns the car engine off, and continues (on the downhill) by inertia. After that, on the next path, he starts ascending a hill again, but because of the inertia, he can drive with turned off engine, path, equal to the half of the previous downhill path.
For example, if we have towns A, B and C. The path between A and B is 10 km, and the bath between B and C is 12 km. Then the driver starts from A, and goes with working engine, the half of the path between A and B (which is 5 km). Then he continues the next 5 km by inertia, and then he enters B and goes to the path between B and C (which is now ascending). But because of the inertia, he can still drive with turned off engine more 2,5 km, and then he must turn his car engine on. Then he continues more 3.5 km with turned on engine (12/2 - 2,5 = 3.5), and then he continues the next 6 km by inertia, and reaches town C. That's it.
So, for the given example, here are how the things are (according to the drawing).
Engine on- A-R (5 km)
Engine off- R-B (5km)
Engine off- B-T (2,5km)
Engine on- T-F (3,5km)
Engine off- F-C (6km)
Notice: if RB == 2*BF, then, for the whole BFC path, the car engine will be off, as there won't be any need to turn it on.
You will have to write a function that will find what is the minimum possible length of the path that the car's engine is on.
Example input 1:
6 7
1 2 10
1 3 5
2 4 8
3 4 7
3 5 11
4 6 6
5 6 9
1 6
Output: 6.00 (path -> 1-3-4-6)
Example input 2:
6 6
1 2 10
2 4 3
4 1 7
3 5 1
3 6 8
5 6 4
1 6
Output: 0
The input file is as follows:
The first line has N and M
The next M lines will have 3 integers- I, J and P, which means that town I is connected to town J and the path is P km.
The last line has two integers- A and B.
The meaning of the input file is:
N -> the number of towns
M -> the number of paths given
A-B -> You are searching the path between town A and town B.
Discuss Contest 8 in the forums
Submission information:
Optimize for: speed
Function prototype (you must have that function!):
public static float Contest8(String fileName);
Send only the function (and all helper functions, if any), to:admin@csharp-home.com
Write this as subject in your e-mail: Contest 8 Solution
End date: 7 April 2006 , 19:00h GMT Time
Please, read the Contest FAQ before submitting or if you have any questions.
Results:
- Results can be found HERE
- This contest has no winner.
If you have any questions and/or comments, please, send them to admin@csharp-home.com
