마법 구슬

시간 제한2초메모리 제한128 MB

요약

주어진 시작 방 M에서 출발해 방 1부터 N까지를 한 번씩 방문하며 연속한 두 방의 차이가 1부터 N-1까지 모두 정확히 한 번씩 나오도록 순서를 구성하는 문제입니다.

문제

한 마법사는 일렬로 놓인 N = 2^m개의 방에서 보물을 최대한 많이 모으려고 한다. 방에는 1번부터 N번까지 번호가 붙어 있고, 각 방에는 보물이 하나씩 있다. 방 사이에는 문이 없어서, 방에 들어가거나 다른 방으로 이동하려면 마법 구슬을 사용해야 한다.

마법사는 IN 구슬 1개, OUT 구슬 1개, 그리고 각 1 <= k <= N-1에 대해 A_k 구슬 1개씩을 가지고 있다.

IN은 반드시 처음에 사용한다. 이 구슬은 마법사를 어떤 방 하나에 들여보낸다. 어느 방에 들어갈지는 미리 알 수 없지만, 들어간 뒤에는 그 방 번호 M을 알 수 있다.
A_k는 현재 방에서 왼쪽 또는 오른쪽으로 정확히 k칸 떨어진 방으로 이동시킨다. 방향은 마법사가 고르며, 도착하는 방은 1번부터 N번 사이에 있어야 한다.
각 구슬은 최대 한 번만 사용할 수 있다.
OUT은 반드시 마지막에 사용하며, 성에서 나가는 데 쓰인다.

방의 개수 N과 처음 들어간 방 M이 주어질 때, 얻을 수 있는 보물의 개수가 최대가 되도록 방문하는 방 번호의 순서를 출력하라. 주어진 조건에서는 모든 방을 정확히 한 번씩 방문할 수 있다.

첫째 줄에 정수 N (2^1 <= N <= 2^13 = 8192)이 주어진다. N은 2의 거듭제곱이다.

둘째 줄에 IN을 사용해 처음 들어간 방 번호 M (1 <= M <= N)이 주어진다.

M에서 시작하여 방문하는 방 번호 N개를 순서대로 한 줄에 출력한다. 인접한 두 방 번호 사이에는 공백을 하나 둔다.

연속해서 출력한 두 방 번호의 차이의 절댓값은 1, 2, ..., N-1을 각각 정확히 한 번씩 사용해야 한다. 가능한 답이 여러 개라면 그중 하나를 출력한다.