시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 44 11 10 34.483%

문제

마술사 견습생 진수에게는 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') 를 출력한다.

sjj번째 셔플이 X-셔플인지 Y-셔플인지를 의미한다.

방법이 여러 가지인 경우 그 중 하나만 출력한다.

예제 입력 1

2
9 6 7
3 1 2

예제 출력 1

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번

  • 문제를 만든 사람: exqt