Woburn Challenge 2002 - Suicidal
Problem 4: The Spell of Lord Ruru
Pressed against the icy mountain Caradhras, trying to dodge yet another avalanche caused by Saruman’s chant, Gandalf began to wonder, "It is as though the trail was getting longer and longer... and steeper and steeper." He focused his power to read the mind of his former master.
"We must turn back!" he yelled through the thundering snow, "We must turn back!"
The fellowship, slightly at loss, obeyed at once.
What Gandalf had realized was shocking, shocking indeed. Not since Lord Ruru has the "mountain raising" spell been used. Lord Ruru, the six-legged Serpent of Doom, used it to torture his subordinates. He would set them off on a mountain trail, and then lower and raise mountains to make the trail indefinitely longer than it seemed, trapping the victim, forever going forth, but never reaching the end.
Lord Ruru's power was unparalleled, so it seemed like Saruman was unable to raise the mountains completely at will. Still, the danger was there.
At his castle's keep, Saruman with his arms raised high in the air, was amidst a chant. His eyes were closed, deeply focused, as he was predicting the trail the fellowship would take - the shortest, of course - and using Lord Ruru's evil spell on that path...
Given a one dimensional mountain range, consisting of a sampling of heights (positive ints), and given that the fellowship must either stay on top of the range and/or cut horizontally across a peak (or peaks) to another place on top of the range, what is the shortest distance that will be traveled?
Oh yeah, if you recall all mountains in Middle-earth have slopes of 45 degrees. Also, Gandalf didn’t bring his “walking-on-air” spell, so the fellowship can’t cut across valleys. If two points of the same elevation appear, assume a horizontal distance of 100 standard units between them, and there will be no more than 30000 samplings of heights!
Input
There will be multiple test cases.
Each test case will consist of a list of heights in the format height #1 height #2 …., terminated by a -1.
The last case will simply be a single -1.
Output
Output the shortest distance that will be traveled by the fellowship.
Your answer should be precise to 3 decimal digits.
Sample Input
0 0 -1
0 10 0 -1
0 10 -1
-1
Sample Output
100.000
20.000
14.142
All Submissions
Best Solutions
Point Value: 25
Time Limit: 2.00s
Memory Limit: 16M
Added: Oct 05, 2008
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
describes the same peak as
0 10 0 -1
The former just samples more heights.