Safe Cracking
Time limit2sMemory limit128 MB
Given N dial values that can be cyclically increased and merged when adjacent and equal, find the minimum total seconds to make all dials equal, considering rotation direction and wraparound.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Divide and conquer, Greedy
- Solved
- No attempts yet
Problem
A safe lock consists of N rotating dials. Each dial has the numbers from 0 to M-1 written around it. If a dial showing M-1 is rotated one more step, it becomes 0.
The safe opens when every dial shows the same number. Dials can only be rotated in the direction that increases their number, and rotating one dial by one step takes 1 second.
A consecutive group of dials that currently show the same number can be rotated together. Regardless of the length of the group, increasing all of them by one step takes 1 second. For example, from the state (1, 1, 1, 2), the three leftmost dials can be rotated together for 1 second so that they all become 2.
Given the initial state of the lock, find the minimum time required to open the safe.
Input
The first line contains N, the number of dials, and M, the number of possible values. (1 ≤ N ≤ 500, 2 ≤ M ≤ 10,000)
The second line contains N integers: the initial numbers shown on the dials.
Output
Print the minimum time required to open the safe.
Hint
For the initial state (9, 0, 1, 0, 3), one possible optimal sequence is:
- Initial state: (9, 0, 1, 0, 3)
- After 1 second: (9, 0, 1, 1, 3)
- After 2 seconds: (0, 0, 1, 1, 3)
- After 3 seconds: (1, 1, 1, 1, 3)
- After 4 seconds: (2, 2, 2, 2, 3)
- After 5 seconds: (3, 3, 3, 3, 3)
So the safe can be opened in 5 seconds.