Capba dreams of one day being a virtuoso trombone soloist... but for now, he must practice his boring exercises, which involve playing N (1 ≤ N ≤ 100000) notes, one after another. A trombone has seven slide positions, numbered closest to furthest from 1 to 7. The ith note can be played in Mi (1 ≤ Mi ≤ 7) different slide positions.
Since he wants to save his energy for more interesting things, he wants to get through the exercise with as little effort as possible. Most importantly, this means minimizing the total distance that the slide moves. If two consecutive notes are played in positions x and y, then the slide moves a distance of |x-y|.
However, if there are multiple ways to play the exercise which minimize the movement of the slide, Capba wants the one which will minimize the number of times the slide must change direction — another important aspect which can reduce the amount of effort. Between two consecutive notes, with the first played in slide position x and the second in position y, the slide is either is moving in (x > y), stationary (x = y), or moving out (x < y).
Given the above criteria, your job is to find a way to play all of the notes in order that minimizes the effort required, and output the total distance travelled by the slide as well as the number of times it changes direction.
Line 1: N
Next N lines: Mi, followed by Mi integers, denoting the slide positions in which note i can be played.
Output two space-separated integers: the total distance travelled by the slide, followed by the number of direction changes, for the best solution.
8 2 1 6 2 3 6 2 1 4 2 3 6 2 1 5 2 2 6 1 4 2 6 1
Twinkle, twinkle, little star (with repeated notes omitted).
Note 1 can be played in either position 1 or 6, note 2 in position 3 or 6, etc.
Notice that the slide positions can be given in any order.
The best option is to play the notes in positions 6, 6, 4, 3, 1, 2, 4, 6. The total distance travelled is 0+2+1+2+1+2+2=10, and there are changes of direction after notes 2 and 5.
Note that other solutions exist which yield a distance of 10, such as always using the furthest slide position — however, they require more changes of direction.
Point Value: 15
Time Limit: 2.00s
Memory Limit: 1024M
Added: Feb 22, 2011
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3