시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 149 | 43 | 40 | 35.398% |
마술사 견습생 진수에게는 N (N은 홀수) 장의 카드가 있고 진수는 두 가지 셔플을 할 줄 안다.
첫 번째 셔플을 X-셔플이라고 하고 셔플을 하는 방법은 다음과 같다.
앞 부분의 (N+1)/2 개와 뒷 부분 (N-1)/2 개로 나눈다.
뒷 부분을 순서대로 앞 부분 사이사이에 끼워넣는다.
두 번째 셔플을 Y-셔플이라고 하고 셔플을 하는 방법은 다음과 같다.
앞 부분의 (N-1)/2 개와 뒷 부분 (N+1)/2 개로 나눈다.
앞 부분을 순서대로 뒷 부분 사이사이에 끼워넣는다.
처음 카드팩을 뜯으면 카드는 앞 부분 부터 차례대로 1번, 2번, ..., N번 카드가 순서대로 있다.
진수는 위의 두 셔플을 사용하여 A번 카드를 앞에서 B번째로 보내는 마술을 하고자 한다.
하지만 카드가 많아질수록 머리가 복잡하여 힘들어 고민하고 있다. 진수를 도와 최소 셔플 방법을 구하자.
첫 번째 줄에 테스트 케이스 개수 T (1 ≤ T ≤ 100) 가 주어진다.
다음 T개 줄에는 각 줄 마다 N, A, B (3 ≤ N < 109, 1 ≤ A, B ≤ N, A ≠ B, N은 홀수) 가 주어진다.
항상 방법이 존재하는 입력만 주어진다.
i번째 줄에는 i번째 테스트 케이스의 최소 횟수로 셔플하는 방법을 나타내는 문자열 S = s1s2 ... sK (sj = 'X
' or 'Y
') 를 출력한다.
sj는 j번째 셔플이 X-셔플인지 Y-셔플인지를 의미한다.
방법이 여러 가지인 경우 그 중 하나만 출력한다.
2 9 6 7 3 1 2
XYX Y
1 2 3 4 5 6 7 8 9
1 6 2 7 3 8 4 9 5
3 1 8 6 4 2 9 7 5
3 2 1 9 8 7 6 5 4
6번 카드가 7번째에 위치하고 한 번 또는 두 번의 셔플로 6번 카드를 7번째 위치로 옮길 수 없으므로 최소 셔플 방법이 된다.
University > 경북대학교 > 2020 Goricon J번