Retype
면접 대비시간 제한20초메모리 제한1024 MB
레벨 수 N, 현재 레벨 K, 검을 얻는 레벨 S가 주어질 때, 1레벨부터 다시 시작하는 경우와 S까지 되돌아가는 경우를 비교해 이미 쓴 시간을 포함한 최소 총 시간을 구한다.
문제
프로그래밍 대회를 오랫동안 준비한 끝에, 당신은 잠시 쉬면서 게임을 하기로 했다. 지금 하고 있는 게임은 Quick Start라는 어드벤처 게임이다.
이 게임에는 N개의 레벨이 있고, 당신은 현재 K번째 레벨에 있다. 그런데 마지막 레벨의 보스를 물리치려면 특별한 검이 필요한데, 그 검은 S번 레벨에서 얻을 수 있다는 사실을 뒤늦게 알게 되었다. 그 레벨은 이미 클리어했지만, 그때 검을 줍는 것을 잊었다.
이제 검을 주우면서 게임을 가능한 한 짧은 시간에 끝내고 싶다. 선택지는 두 가지다.
- 게임을 다시 시작해서 1번 레벨부터 모든 레벨을 다시 클리어한다.
- S번 레벨에 도달할 때까지 이전 레벨로 거슬러 올라가서 검을 줍고, S번 레벨부터 남은 모든 레벨을 클리어한다.
레벨에 들어갈 때마다 반드시 나와야 한다. 레벨을 클리어하고 다음 레벨로 넘어가거나, 이전 레벨로 이동하거나, 게임을 끝내고 나가는 방식이다. 어떤 레벨에서 나오는 데는 1분이 걸린다. 예를 들어 처음 L개의 레벨을 클리어하는 데 L분이 걸린다.
당신의 임무는 게임을 끝내는 데 필요한 총 시간(지금까지 쓴 시간 포함)이 가장 적어지는 선택지를 알아내는 것이다.
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 그다음 T개의 테스트 케이스가 이어진다.
각 테스트 케이스의 첫 줄(이자 유일한 줄)에는 세 정수 N, K, S가 주어진다. 각각 게임의 레벨 수, 현재 있는 레벨, 검을 주워야 하는 레벨이다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 게임을 끝내는 데 필요한 최소 총 시간이다.
제한
- 1 ≤ T ≤ 100.
- 1 ≤ S < K < N.
힌트
예제 1에서 처음 4개 레벨을 클리어하고 5번째 레벨에 들어가는 데 4분이 걸렸다. 게임을 다시 시작해서 모든 레벨을 다시 클리어하면 11분이 더 걸리고(다시 시작하는 데 1분, 10개 레벨을 클리어하는 데 10분), 합계 15분이 된다. 다른 선택지는 2번 레벨에 도달할 때까지 뒤로 이동하고(3분), 남은 모든 레벨을 클리어하는 것(9분)으로, 총 16분이 된다.
예제 2에서 처음 6개 레벨을 클리어하고 7번째 레벨에 들어가는 데 6분이 걸렸다. 6번 레벨에 도달할 때까지 뒤로 이동하고(1분), 남은 모든 레벨을 클리어하면(5분) 게임을 끝내는 데 총 12분이 걸린다.