다이얼 자물쇠
면접 대비시간 제한40초메모리 제한1024 MB
1부터 N까지 순환하는 값을 가진 W개의 바퀴 위치가 주어질 때, 모든 바퀴가 같은 값이 되도록 이동하는 최소 총 이동 횟수를 구한다.
문제
다이얼 자물쇠에 W개의 바퀴가 있고, 각 바퀴에는 1부터 N까지의 정수가 오름차순으로 적혀 있다.
어느 순간이든 각 바퀴는 특정한 값을 보여준다. Xi는 i번째 바퀴가 처음에 보여주는 값이다.
한 번의 이동으로 바퀴의 값을 X에서 X+1 또는 X-1로 바꿀 수 있으며, 1과 N 사이는 순환한다. 예를 들어 바퀴가 지금 1을 보여준다면, 한 번의 이동으로 값을 2 또는 N으로 바꿀 수 있다.
모든 바퀴의 초기 값이 주어질 때, 모든 바퀴가 같은 값을 보여주게 하려면 최소 몇 번 이동해야 하는가?
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다.
각 테스트 케이스의 첫 줄에는 두 정수 W와 N이 주어진다.
둘째 줄에는 W개의 정수가 주어진다. i번째 정수는 Xi이다.
출력
각 테스트 케이스마다 Case #x: y를 한 줄에 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 모든 바퀴가 같은 값을 보여주게 하는 최소 이동 횟수이다.
제한
- 1 ≤ T ≤ 100.
- 1 ≤ Xi ≤ N.
힌트
예제 1에서 가장 좋은 방법은 모든 바퀴가 3을 보여주게 하는 것이고, 총 2번 이동한다. 첫 번째 바퀴는 한 번 이동하고(2에서 3으로), 두 번째 바퀴는 이동하지 않으며(이미 3을 보여준다), 세 번째 바퀴는 한 번 이동한다(4에서 3으로).
참고로 모든 바퀴가 1을 보여주게 하려면 5번, 2를 보여주게 하려면 3번, 4를 보여주게 하려면 3번, 5를 보여주게 하려면 5번 이동한다.
예제 2에서 가장 좋은 방법은 모든 바퀴가 1, 2, 9, 10 중 하나를 보여주게 하는 것이고, 총 8번 이동한다.