마법 구슬 |
---|
해리포터는 마법의 성의 방들에 있는 보물들을 최대한 많이 가져올 계획을 세우고 있다. 마법의 성에는 일렬로 되어있는 N = 2m개의 방이 있으며, 모든 방에는 보물이 하나씩 존재한다. 이 방들에는 문이 없고 출입하기 위해서는 마법 구슬을 이용하는 길밖에 없다. 해리포터에게는 N+1개의 마법 구슬이 있는데, IN으로 표시되는 마법 구슬과 A1, A2, ..., AN-1으로 표시되는 N-1개의 마법 구슬과 OUT으로 표시되는 마법 구슬이 있다. 각 마법 구슬들은 다음과 같은 특징을 가진다.
예를 들어, N=4인 경우에 IN, A1, A2, A3, 및 OUT의 총 5개의 마법 구슬들이 해리포터에게 주어져 있고, IN을 사용했더니 3번방에 들어가게 되었다고 하자. 이 때, 그는 다음과 같은 방법으로 마법 구슬을 이용하여 방들에 있는 4개의 보물을 찾아 가져올 수 있다.
또 다른 예로, N=4인 경우에 IN을 이용했더니 1번방에 들어가게 되었다고 하자. 이 때는 다음의 방법으로 방들에 있는 4개의 보물을 찾아 가져올 수 있다.
마법의 성에 있는 방들의 개수 N과 해리포터가 IN을 사용하여 들어간 방의 위치가 주어졌을 때, 그가 마법 구슬 A1, ⋯,AN-1및 OUT을 이용해서 방들에 있는 보물을 최대한 많이 찾아 가져오기 위하여 들어간 방의 순서를 구하는 프로그램을 작성하시오. |
입력 | |
---|---|
첫째 줄에 방의 개수를 나타내는 정수 N (단, 21 ≤ N ≤ 213=8192)이 주어진다. N은 2의 거듭제곱인 정수이다. 둘째 줄에는 해리 포터가 IN을 사용해 들어간 방의 번호를 나타내는 정수 M이 주어진다. (단, 1 ≤ M ≤ N) |
출력 | |
---|---|
해리 포터가 처음 들어간 방에서 시작하여, 방들에 있는 보물을 최대한 많이 찾아오기 위하여 들어간 방 번호들을 순서대로 한 줄에 출력한다. 각 방 번호사이에는 빈칸을 한개 둔다. 답이 여러 개인 경우에는 그 중 하나만 출력한다. |
예시 | |||
---|---|---|---|
1 | 입력 | 4 3 | |
출력 | 3 2 4 1 |