16684번 - 하노삼의 탑 서브태스크

COSE214 알고리즘 강의를 수강하는 이세정 군은 최근 강의에서 ‘하노이의 탑’ 문제를 해결하는 방법에 대해 배웠다. 하노이의 탑의 규칙은 아래와 같다.

• 기둥은 3개이며 왼쪽부터 차례로 1, 2, 3번 기둥이다.
• N개의 서로 다른 크기의 원판이 쌓여 있으며, 작은 원판 위에 큰 원판이 올라갈 수 없다.
• 각 원판은 1번부터 N번까지 번호가 있으며, 이 번호가 클수록 원판의 크기가 크다.
• 한 번에 한 개의 원판만 옮길 수 있으며 한 번의 이동에는 1초가 소요된다.
• 1번 기둥에서 3번 기둥으로 모든 원판을 최소 횟수로 옮겨야 한다.
• <1> 원판은 어느 기둥에서 어느 기둥으로든 자유롭게 옮길 수 있다.

그런데 갑자기 옆에 앉아 있던 삼세정 군이 자신만의 규칙을 만들고 싶다며, <1> 대신 아래와 같은 조건을 적용하면 어떻게 될지 궁금해 했다.

• <2> 원판을 인접한 기둥으로만 옮길 수 있다. (1번 ↔ 2번 ↔ 3번)

반대쪽에 있던 사세정 군은 다음과 같은 규칙을 제안했다.

• <3> 원판을 오른쪽 기둥으로만(단, 3번에서는 1번으로) 옮길 수 있다. (1번 → 2번 → 3번 → 1번)

그들은 신난다며 이 문제를 ‘하노삼의 탑’으로 명명했다. 이세정 군은 솔직히 이런 추가 조건들이 끌리지 않았지만, 그래도 인싸가 되기 위해 K초 후에 각 원판이 어디에 배치되어 있을지 구해보기로 했다. 그를 도와주자.

첫째 줄에 세 정수 M, N, K 가 공백으로 구분되어 주어진다.

M은 하노삼의 탑에 대해 적용될 규칙의 번호를 나타낸다. 1 ≤ M ≤ 3 이며, 1이라면 원래의 문제, 2라면 삼세정 군의 규칙, 3이라면 사세정 군의 규칙을 적용한다.

N과 K는 M의 값에 따라 범위가 달라진다. 상세한 범위는 다음과 같다.

• M = 1인 경우: 1 ≤ N ≤ 60, 0 ≤ K ≤ 2^N-1
• M = 2인 경우: 1 ≤ N ≤ 40, 0 ≤ K ≤ 3^N-1
• M = 3인 경우: 1 ≤ N ≤ 30, 0 ≤ K ≤ $\frac{3+2\sqrt{3}}{6}(1+\sqrt{3})^N+\frac{3-2\sqrt{3}}{6}(1-\sqrt{3})^N-1$

첫 번째 줄에 N개의 정수 a₁, a₂, ..., a_N 을 공백으로 구분하여 출력한다. a_i 는 K 초 후 i번 원판이 위치한 기둥의 번호이다.

K ≤ 1,000을 만족한다.

문제 입력에서 주어진 조건 외에 추가적인 조건이 없다.