JUST PRACTICE DANCE
All submissions for this problem are available.
Mr. Pannase wants to participate in a dance show but he's really poor in dancing.Also , he's fat and too lazy to even move his feet around.What he does know is programming.So he is considering writing a program to plan the movement sequence of his feet,so that he may save his strength on dancing.Now he looks forward to dancing easily than sweatily.
"Just Practice Dance" is a game that requires the dancer to use his feet to tread on the points according to the direction sequence in the game.There is one central and four side points in the game.Those side points are classified as top,left,bottom and right.For the sake of explanation,we represent them as integers.That is, the central point is 0, the top is 1,the left is 2,the bottom is 3 and the right is 4.
At the beginning the dancer's two feet stay on the central point. According to the direction sequence, the dancer has to moveone of his feet to the special points.For example, if the sequence requires him to move to the top point at first,he may move either of his feet from point 0 to point 1(Note : not both of his feet) .Also, if the sequence then requires him to move to the bottom point,he may move either of his feet to point 3(bottom),regardless whether to use the foot that stays on point 0 or the one that stays on point 1.
There is a strange rule in the game : moving both of his feet to the same point is not allowed.For instance, if the sequence requires the dancer to the bottom pointand one of his feet already stays on point 3,he should stay the very foot on the same point and tread again, instead of moving the other one to point 3.
After dancing a long time,Mr. Pannase can calculate how much strength will be consumed when he moves from one point to the other.Moving one of his feet from the central point to any side points will consume 2 units of his strength.Moving from side point to another adjacent side point will consume 3 units, such as from top to the left point.Moving from one side point to the opposite side point will consume 4 units,such as from the top point to the bottom point.Yet , if he stays on the same point and treads again,he will use 1 unit.
Assume the sequence requires Mr. Pannase to move to points 1->2->2->4. His feet may stay on (point 0,point 0)->(0,1)->(2,1)->(2,1)->(2,4).In this couple of integers,the former number represents the point of his left foot, and the latter represents the point of his right foot.In this way he has to consume 8 units of his strength.If he tries another pass, he will have to consume much more strength. The 8 units of strength is the least cost.
The input would consist of a series of direction sequences.Each direction sequence contains a sequence of numbers.Each number should either be 1, 2 ,3 or 4 and each represents one of the four directions.A value of 0 in the direction sequence indicates the end of the direction sequence.And this value should be excluded from the direction sequence.The input ends if the sequence contains a single 0.
For each direction sequence,print the least units of strength that would be consumed.The result should be a single integer on a line by itself.Any more white spaces or blank lines are not allowed.
Input: 1 2 2 4 0 1 2 3 4 1 2 3 3 4 2 0 0 Output: 8 22
|Time Limit:||0.12 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.