시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 95 28 26 48.148%

문제

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과 KM의 값에 따라 범위가 달라진다. 상세한 범위는 다음과 같다.

  • M = 1인 경우: 1 ≤ N ≤ 60, 0 ≤ K ≤ 2N-1
  • M = 2인 경우: 1 ≤ N ≤ 40, 0 ≤ K ≤ 3N-1
  • = 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개의 정수 a1, a2, ..., aN 을 공백으로 구분하여 출력한다. ai 는 K 초 후 i번 원판이 위치한 기둥의 번호이다.

서브태스크 1 (150점)

K ≤ 1,000을 만족한다.

서브태스크 2 (450점)

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

예제 입력 1

1 3 6

예제 출력 1

1 3 3
| | |
| | 2
1 | 3
-----

예제 입력 2

1 4 1

예제 출력 2

2 1 1 1

예제 입력 3

2 3 6

예제 출력 3

1 3 1
| | |
1 | |
3 | 2
-----

예제 입력 4

2 4 1

예제 출력 4

2 1 1 1

예제 입력 5

3 3 6

예제 출력 5

2 3 1
| | |
| | |
3 1 2
-----

예제 입력 6

3 4 1

예제 출력 6

2 1 1 1

채점

  • 예제는 채점하지 않는다.