问题
하노이 탑 문제를 들어 보았을 것이다.
3개의 막대기 중 하나에 n개의 원판이 꽂혀 있고, 이 원판들을 다른 막대기로 옮기는 문제이다.
이 문제를 풀 때의 이동 회수가 2n-1임은 잘 알려져 있다.
하노이 탑에서 n개의 원판이 있을 경우에 이 원판의 이동 경로를 모두 출력하는 프로그램을 만드는 것은 쉬운 일이다.
하지만 n이 커지면 출력 개수가 2n-1이기 때문에 출력하지 못한다. (일반적인 하노이 문제와 같이 막대는 항상 3개로 한다.)
당신이 할 일은, 원판이 n개 있을 때, 최소한의 횟수로 이동시키는 방법 중에서, k번째에 어떤 작업을 수행해야 하는지를 출력하는 것이다.
k번째만을 출력하면 된다. 물론 k는 1에서 2n-1까지의 정수이다. 제한시간은 2초이다.
输入
첫째 줄에 디스크의 수를 정수 n(1 ≤ n ≤60)과 몇 번째 이동값k(1 ≤ k ≤ 2n-1)가 주어진다.
각 디스크들의 번호는 1, 2, ..., n이며, 잘못된 입력은 주어지지 않는다.
输出
k번째 순서에서 몇 번째 원판을 몇 번째 막대기에서 몇 번째 막대기로 이동시키는지 출력한다.
예를 들면 3번 원판을 1번 막대에서 2번 막대로 움직일 경우엔 3 : 1 -> 2 로 출력한다.
숫자와 : -> 사이는 공백으로 구분하며 ->내부에는 공백이 없어야한다.
示例 #1
3 4
3 : 1 -> 3
示例 #2
4 10
2 : 2 -> 1
来源
경기도 정보올림피아드 알고리즘
需要登录才能编写代码。