Informatica Online Judge

  지게차로 상자쌓기 아르바이트 [2125 / 084D]

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


The Champion of this Problem (C++) : gs16109 - 0ms / 533byte
My Best Submission (C++) : N/A

[koistudy.net (JKJeong 2017)]

Background

경곽이는 상자 쌓기 아르바이트를 한다.

크기가 $1$부터 $n$까지의 $n$개의 상자가 $3$개의 야적장 $A$, $B$, $C$에 나뉘어져 쌓여있다.

상자들은 다음과 같은 특징을 가진다.

============================================================================================

- $1$번 상자의 무게는 $1$ $kg$이다.

- 각 $i$번 상자의 무게는 $i-1$번 상자의 무게의 2배이다. 즉 $w_i = 2w_{i-1}$ 이다. (단, $i>1$)

- 상자는 지게차를 이용해서 야적장 가장 위에 있는 상자를 한 번에 하나씩만 옮길 수 있다.

- 임의의 상자 위에 다른 상자들을 쌓을 수 있다.
(단, 쌓고자 하는 상자들의 무게 합이 자기 자신보다 작아야 한다.
즉, $i$번 상자 위에 $n$개의 상자들이 쌓으려고 한다면 다음 조건을 만족해야 한다. $w_i > \sum_{j=1}^{n}w_{j}$ )

============================================================================================

위 조건들을 만족하면서 모든 상자들을 $C$ 야적장으로 옮기고자 한다.

최소 횟수를 구하고 옮기는 과정을 출력하는 프로그램을 작성하시오.

Input

첫 번째 줄에 상자의 수 $n$이 입력된다.

두 번째 줄에는 야적장 $A$에 현재 쌓여 있는 상자들의 정보가 입력된다.

세 번째 줄에는 야적장 $B$에 현재 쌓여 있는 상자들의 정보가 입력된다.

마지막 번째 줄에는 야적장 $C$에 현재 쌓여 있는 상자들의 정보가 입력된다.

각 세줄에 입력되는 상자들의 정보는 현재 야적장에 쌓여 있는 상자의 수와 각 상자의 번호가 오름차순으로 입력되며 공백으로 구분되어 입력된다.

[입력값의 정의역]

$1≤n≤16$

Output

첫 번째 줄에 옮겨야 하는 최소 횟수를 출력한다.

두 번째 줄부터 한 줄에 한 번씩 입출력 예시와 같이 옮기는 과정을 출력한다.

횟수는 같지만 과정이 다양할 경우 아무 거나 출력하면 된다.

IO Example

입력
2
1 1
1 2
0

출력
2
move box 2 from B to C
move box 1 from A to C

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