JOIN

 Problem Statement

Problem Statement for CombinationLockDiv1

Problem Statement

Andrew has a combination lock. The lock consists of multiple dials that are placed next to each other. Each dial contains the digits 0 through 9, in order. At any moment, exactly one of the digits on each dial is visible. The string formed by the currently visible digits is called the current combination.

The visible digit on a dial can be changed by rotating the dial up or down. Rotating the dial up changes 0 to 1, 1 to 2, and so on. Note that the digits on a dial wrap around: if we rotate up a dial that shows a 9, it will show a 0 again. Naturally, rotating the dial down changes the digit in the other direction.

We are able to rotate multiple dials at the same time, as long as they are next to each other. More precisely, in a single turn we can take an arbitrarily long segment of consecutive dials, and rotate all of them one step in the same direction (i.e., either all of them up, or all of them down).

For example, suppose that the current combination is "123". In one step, we can change it to many different combinations, including "012" (all three dials down), "234" (all three dials up), "133" (middle dial up), and "013" (first two dials down). Note that we cannot change "123" to "224" in a single step.

You are given two String[]s: P and Q. Concatenate the elements of P to get S. S is the current combination. Concatenate the elements of Q to get T. T is the secret combination that unlocks the lock. That is, to open the lock we need to change S into T by rotating some of the dials. Return the smallest number of steps needed.

Definition

 Class: CombinationLockDiv1 Method: minimumMoves Parameters: String[], String[] Returns: int Method signature: int minimumMoves(String[] P, String[] Q) (be sure your method is public)

Constraints

-P and Q will each contain no more than 50 elements.
-Each element of P and Q will contain no more than 50 characters.
-S will contain at least 1 character.
-S will contain the same number of characters as T.
-Each character in S and T will be a digit ('0'-'9').

Examples

0)

 `{"123"}` `{"112"}`
`Returns: 1`
 Rotate the last two dials down.
1)

 `{"1"}` `{"7"}`
`Returns: 4`
 Rotate the dial down 4 times: from 1 to 0, from 0 to 9, from 9 to 8, and from 8 to 7.
2)

 `{"6","07"}` `{"","60","7"}`
`Returns: 0`
3)

 `{"1234"}` `{"4567"}`
`Returns: 3`
4)

 `{"020"}` `{"909"}`
`Returns: 2`
5)

 `{"4423232218340"}` `{"6290421476245"}`
`Returns: 18`

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
Single Round Match 607 Round 1 - Division I, Level Two