페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#10395

붙이기 정렬 10s 1024MB

문제

정수 리스트 \mathbf{X_1}, \mathbf{X_2}, \dots, \mathbf{X_N}가 있다. 우리는 이들이 엄격히 증가하는 순서(Strictly Increasing)가 되기를 원하지만, 불행히도 순서를 바꿀 수는 없다. 즉, 일반적인 정렬 알고리즘은 사용할 수 없다.

우리가 할 수 있는 유일한 일은, 각 정수의 오른쪽에(10진법에서) 숫자 0부터 9까지를 덧붙이는 것이다. 예를 들어 어떤 정수가 10이라면, 한 번의 덧붙이기 연산으로 10\textbf{0} 또는 10\textbf{9}로 만들 수 있고, 두 번의 연산으로 10\textbf{34}로 만들 수도 있다(아래 그림 참고).

현재 리스트가 주어질 때, 리스트가 엄격히 증가하도록 만들기 위해 필요한 "한 자리 덧붙이기" 연산의 최소 횟수는 얼마인가?

예를 들어 리스트가 100, 7, 10이라면, 다음 그림이 보여주듯 총 4번의 연산으로 정렬된 리스트로 만들 수 있다.

Sample Case #1


입력

입력의 첫 줄에는 테스트 케이스 수 \mathbf{T}가 주어진다. \mathbf{T}개의 테스트 케이스가 이어진다. 각 테스트 케이스는 2줄로 설명된다. 첫 줄에는 정수 \mathbf{N}이 주어지며, 리스트에 있는 정수의 개수이다. 둘째 줄에는 \mathbf{N}개의 정수 \mathbf{X_1}, \mathbf{X_2}, \dots, \mathbf{X_N}이 주어지며, 리스트의 원소들이다.


출력

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y는 리스트가 엄격히 증가하도록 만들기 위해 필요한 한 자리 덧붙이기 연산의 최소 횟수이다.


예제 

4
3
100 7 10
2
10 10
3
4 19 1
3
1 2 3
Case #1: 4
Case #2: 1
Case #3: 2
Case #4: 0
샘플 케이스 #1에서는 입력이 문제 설명의 예와 동일하다. 그림이 보여주듯이, 리스트는 4번의 연산으로 정렬된 리스트로 바뀔 수 있다. 마지막 두 정수는 최소 3자리여야 하므로(총 3번 이상의 append 연산 필요) 이를 유의하라. 모든 최종 숫자가 정확히 3자리라고 가정하면 두 번째 숫자가 7로 시작하고 세 번째 숫자가 1로 시작하므로 두 번째가 더 커진다. 따라서 4번보다 적게는 불가능하다. 샘플 케이스 #2에서는 리스트가 엄격히 증가해야 하므로 최소 한 번의 연산이 필요함을 유의하라. 이 경우 두 번째 정수에 어떤 유효한 append 연산을 하든 가능하다. 샘플 케이스 #3에서는 두 번의 append 연산으로 리스트를 4, 19, 1\textbf{93}으로 만들 수 있다. 샘플 케이스 #4에서는 주어진 리스트가 이미 엄격히 증가하므로 연산이 필요 없다.

출처

GCJ 2021r1a A

로그인해야 코드를 작성할 수 있어요.