다음 이진 트리 찾기

모든 컴퓨터과학 전공자는 이진 트리에 익숙하다. 여기서는 이진 트리를 다음과 같이 귀납적으로 정의한다. 이진 트리 $t$는 외부 노드(잎) $\circ$ 이거나, 왼쪽 서브트리 $t_1$과 오른쪽 서브트리 $t_2$를 갖는 내부 노드 $\bullet$를 나타내는 순서쌍 $t = (t_1, t_2)$ 이다. 이 정의에 따르면 모든 이진 트리의 노드 수는 항상 홀수이다.

홀수 $n$에 대하여, $B(n)$을 (내부 노드와 외부 노드를 합쳐) 정확히 $n$개의 노드를 갖는 모든 이진 트리의 집합이라 하자. 예를 들어 $B(1)$은 트리 $\circ$ 하나만을 원소로 가지며, $B(3) = {(\circ,\circ)}$, $B(5) = {(\circ,(\circ,\circ)),\ ((\circ,\circ),\circ)}$ 이다. $B(5)$의 두 트리는 아래 그림에 나타나 있다.

$|t|$를 트리 $t$의 노드 수라 하자. 각 트리 $t$에 대하여 고유한 정수 식별자 $N(t)$를 다음과 같이 정의한다.

• $N(\circ) = 0$
• $N(t_1, t_2) = 2^{|t_1| + |t_2|} + 2^{|t_2|} \cdot N(t_1) + N(t_2)$

예를 들어 $N(\circ, \circ) = 2^{2} + 2^{1} \cdot 0 + 0 = 4$, $N(\circ, (\circ,\circ)) = 2^{4} + 2^{3} \cdot 0 + 4 = 20$, $N((\circ,\circ), \circ) = 2^{4} + 2^{1} \cdot 4 + 0 = 24$ 이다.

이제 모든 이진 트리 위에 정의된 다음 선형 순서를 생각하자.

• 모든 트리 $t$에 대하여 $\circ \preceq t$
• $t_1 \prec u_1$ 이거나, $t_1 = u_1$ 이면서 $t_2 \preceq u_2$ 일 때 $(t_1, t_2) \preceq (u_1, u_2)$

이 순서에서 잎 하나는 가장 작은 트리이다. 두 내부 노드 트리 중에서는 왼쪽 서브트리가 더 작은 쪽이 더 작고, 왼쪽 서브트리가 같다면 오른쪽 서브트리가 더 작은 쪽이 더 작다. 따라서 예를 들어 $\circ \prec (\circ,\circ)$ 이므로 $(\circ,(\circ,\circ)) \prec ((\circ,\circ),\circ)$ 이다.

이제 $B(n)$의 트리들을 $\preceq$ 에 따라 정렬했다고 하자. $B(n)$의 각 트리 $t$에 대하여, $t$의 다음 트리(successor)는 이 정렬에서 $t$ 바로 뒤에 오는 트리이다. 만약 $t$가 $B(n)$에서 가장 큰 트리라면, 그 다음 트리는 $B(n)$에서 가장 작은 트리로 정의한다. 예를 들어 $B(3)$에서 $(\circ,\circ)$의 다음 트리는 자기 자신인 $(\circ,\circ)$ 이고, $B(5)$에서 $(\circ,(\circ,\circ))$의 다음 트리는 $((\circ,\circ),\circ)$ 이다.

트리 $t$의 식별자가 주어질 때, $B(|t|)$에서 $t$의 다음 트리의 식별자를 구하여라.

다음을 수행하는 프로그램을 작성하라.

• 이진 트리 $t$의 식별자를 읽는다,
• $B(|t|)$에서 $t$의 다음 트리의 식별자를 계산한다,
• 그 식별자를 출력한다.

입력의 유일한 줄에 정수 $n$ ($0 \le n \le 2^{30}$)이 주어진다. 이는 어떤 이진 트리 $t$의 식별자이며, 항상 유효한 트리 식별자임이 보장된다.

$B(|t|)$에서 $t$의 다음 트리의 식별자인 정수 $s$ 하나를 출력한다.