Connection Status:
Competition Arena > BikeLock

BikeLock

SRM 245 · 2005-06-01 · by vorthys

SRM 245 · 2005-06-01 · by vorthys · Dynamic Programming
Class Name: BikeLock
Return Type: int
Method Name: minTurns
Arg Types: (string, string)
Problem Statement

Problem Statement

One kind of combination lock often used on bicycles and notebook computers consists of several parallel disks with the digits '0' to '9' printed in order on the outside surface of the disks. To dial a combination, you turn the disks so that the appropriate digit on each disk lines up with a reference mark. Each time you turn a disk, you rotate it up to three positions clockwise or counterclockwise. By grasping several disks with your fingertips, you can simultaneously turn up to three adjacent disks by the same amount. Note that '0' and '9' are adjacent on the disks.

Given the current numbers showing on each disk (as a String) and the desired numbers (also as a String), find the minimum number of turns needed to dial the desired combination. For example, if the current numbers are "555" and the desired numbers are "464", then one way to dial the combination would be to turn each disk separately, taking 3 turns altogether. However, a better way to dial the combination is to turn all three disks simultaneously to "444" and then turn the middle disk by itself to "6", taking 2 turns altogether.

Constraints

  • current contains between 3 and 50 characters, inclusive.
  • desired is the same length as current.
  • current contains only digits ('0'-'9').
  • desired contains only digits ('0'-'9').
Examples
0)
"123"
"123"
Returns: 0
1)
"123"
"456"
Returns: 1
2)
"555"
"464"
Returns: 2

The example above.

3)
"01234567890123456789012345678901234567890123456789"
"12039487120394812461274912846192836491827649819864"
Returns: 38
4)
"555"
"737"
Returns: 3
5)
"1234"
"3456"
Returns: 2

If you could turn four disks simultaneously, you could do this in 1 turn. But you can't turn more than three disks at once, so it takes 2 turns.

Submissions are judged against all 69 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class BikeLock with a public method int minTurns(string current, string desired) · 69 test cases · 2 s / 256 MB per case

Submitting as anonymous