Door to Secret
Time Limit: 2 Seconds
Memory Limit: 65536 KB
An expedition was exploring an ancient ruin. They met a closed door and believed
there might be some secrets behind. But the door seemed to be sealed by some ancient
magic and immune to physical action. The explorers tried their best to open it:
They smashed the door with hammer, burnt it with fire, shot it with gun,
all of which, of course, turned out to be a waste of time.
They were just about to give up, when one of them spotted something special. "Look,
what is this?" he yelled. There was a line of white stones on the ground.
On the top of those stones, some strange symbols were engraved. There was an
archaeologist among the explorers, who was an expert of this ancient civilization.
Reading the symbols, he claimed that the stones were the key to this door. He
knocked on the stones one by one; each gave a different tone. The archaeologist continued
with his research. Then he found out that they should knock the stones in two passes.
The former was from left to right, starting from the leftmost stone; the latter from
right to left, starting from the rightmost stone. Every stone should be knocked exactly once.
If they could keep the sum of tone difference between two consecutive knocks as small
as possible, the door would open. Now it is your task. Given the tones of all the stones,
find out the minimum sum of tone difference.
Notice that the first knock of second pass and the last knock of first pass are also
considered to be consecutive.
Input contains multiple test cases. The first line of each test case is a
positive integer n (2 <= n <= 100) - the number of stones. The second
line contains n positive integer - the tone of each stone.
The last test case is followed by a zero.
For each test case, print a single line with the minimum sum of tone difference
mentioned in the problem.
1 2 3 4 5
Author: XU, Chuan
Source: Zhejiang University Local Contest 2004