Informatica Online Judge

  가장 긴 하노이 [1313 / 0521]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 227   Total Tried : 159


The Champion of this Problem (C++) : tlsdydaud1 - ms / 279byte
My Best Submission (C++) : N/A

[JKJeong 2015]

Background

하노이 타워는 잘 알려진 퍼즐이다.

이번에 다루는 하노이 타워는 다음 그림과 같이 A영역의 원판을 모두 B영역으로 보내는 것이 목적이다.





물론 규칙은 다음과 같이 2가지로 일반하노이와 동일하다.

규칙1. 한 번에 하나의 원판만 옮길 수 있다. (물론 제일 위에 있는 원판)
규칙2. 작은 원판 위에 큰 원판을 올릴 수는 없다.


자!! 여기서 새로운 제약이 하나 붙는다. 시작으로부터 끝까지 옮기는 동안 단순경로(simple path)로 옮겨야 한다.

단순경로란 방문한 정점을 방문하지 않으면서 이동하는 경로를 말한다. 하노이 타워에서는 같은 상태를 거치지 않으면서 원판을 옮기는 것을 말한다.

즉 A위치에 1, 3번 원판이 위치하고 B위치에 2번 원판이 있다면, 나중에 옮기는 도중에 이와 같은 상태를 다시 거칠 수 없다. ㅠㅠ

원래 일반 하노이 자체가 최소 이동으로 옮겨야 하기 때문에 단순 경로로 옮겨야 한다.

하지만 이번에는 단순경로로 옮기되 가능한 한 이동 횟수를 늘려야 한다. 즉 가능한 최대 횟수로 옮기는 것이 목적이다.

그리고 이동 경로까지 출력해야 한다. 이를 처리하는 프로그램을 작성하시오.

Input

첫 번째 줄에 원판의 수 n을 입력받는다.

[입력값의 정의역]
1 <= n <= 10,000,000

Output

출력 예시를 참고하여 이동경로를 한 줄에 하나씩 출력한 후, 최대 이동횟수를 출력한다.

단, 이동경로가 너무 많기 때문에 경로가 100줄을 넘을 경우 100줄까지만 출력한다. 그리고 이동 횟수도 엄청나게 증가하기 때문에 1,000,000,007로 나눈 나머지를 출력한다.

IO Example

입력
1

출력
1 : A->C
1 : C->B
2

* 설명 : 같은 상태를 거치지 않으면서 최대로 이동할 수 있는 것은 2회이다. 그 예는 다음 그림과 같다.



Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]