런, 런, 런어라운드 수
시간 제한1초메모리 제한128 MB
2자리에서 7자리 사이의 수 R마다, 서로 다른 1에서 9 사이의 숫자로 이루어지고 이동이 순환하며 모든 자리를 한 번씩 방문한 뒤 시작점으로 돌아오는 runaround 수 중 R 이상인 가장 작은 값을 찾는다.
문제
N자리 런어라운드 수(runaround number)는 다음과 같이 정의된다.
- 정확히 N개의 자리로 이루어진 정수이며, 각 자리의 숫자는 1 이상 9 이하이다.
- 각 자리의 숫자는 수열에서 다음 숫자가 어디에 있는지를 알려 준다. 즉, 그 숫자만큼 오른쪽으로 이동하면 수열의 다음 숫자에 도달한다. 필요하면 가장 오른쪽 자리에서 가장 왼쪽 자리로 순환(wrap around)한다.
- 가장 왼쪽 자리의 숫자가 수열의 첫 번째 숫자이며, 수의 모든 자리를 정확히 한 번씩 사용한 뒤 다시 이 첫 번째 숫자로 돌아와야 한다.
- 같은 숫자가 두 번 이상 나타나지 않는다.
예를 들어 81362가 런어라운드 수인지 다음과 같이 확인한다.
- 가장 왼쪽 자리 8에서 시작한다.
8 1 3 6 2 - - 오른쪽으로 8칸 이동하여 6에 도달한다(순환에 주의).
8 1 3 6 2 - - - 오른쪽으로 6칸 이동하여 2에 도달한다.
8 1 3 6 2 - - - - 오른쪽으로 2칸 이동하여 1에 도달한다.
8 1 3 6 2 - - - - - 오른쪽으로 1칸 이동하여 3에 도달한다.
8 1 3 6 2 - - - - - - 오른쪽으로 3칸 이동하여 시작점인 8로 돌아온다.
8 1 3 6 2 = - - - -
입력
한 줄에 하나씩, 2자리 이상 7자리 이하의 정수 R이 하나 이상 주어진다. 각 R에 대해 R 이상인 가장 작은 런어라운드 수를 구하라. 모든 입력값에 대해 그러한 수는 항상 존재한다. 입력의 마지막 줄에는 첫 번째 칸에 숫자 0만 주어지며, 이 줄은 처리하지 않는다.
출력
각 입력값에 대해 순서대로 Case k: X 형식으로 한 줄씩 출력한다. 여기서 k는 질의의 1부터 시작하는 순번이고, X는 그 질의의 R 이상인 가장 작은 런어라운드 수이다.