ZOJ Problem Set - 3463
Minami is a pianist. Both her left and right hands can touch at most 9 keys and should occupy at least 5 keys from the thumb to the little finger.
Now she wants to play a simple piano piece on a piano which has 52 white-keys and 36 black-keys. The piece is easy because she should only hit one key. If she can't touch one key, she should move her arm. Moving arm costs her f(x) energy. f(x) is a function about the distance of the thumb's moving, x: f(x) = floor(sqrt(x)).
Now you are given the keys where her left and right thumbs are, and the compose containing only numbers instead of notes. All numbers in the compose are from 0 to 51 indicating the 52 white-keys on the piano. The number 0 denotes the left most key. When playing the piano, The left hand can be on the right side. But, one finger touching the key between two fingers of the other hand is fobidden.
Output the minimal energy cost.
There are no more than 20 cases. For each case, the first line contains 3 integers L, R, N (4 ≤ L ≤ 51, 0 ≤ R ≤ 47, 1 ≤ N ≤ 1000). L and R indicate the keys where her left and right thumbs are before playing. There are N lines followed. Each line contains one integer indicating the key Minami should play next.
Output the minimal energy cost in a single line.
10 20 10 0 1 2 3 4 5 6 7 8 9
Author: YU, Xiaoyao
Contest: ZOJ Monthly, January 2011