Informatica Online Judge

  Stacking CUP [0536 / 0218]

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


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

[]

Background

크기가 서로 다른 n개의 컵과 3개의 접시 a, b, c가 있다.

각각의 컵은 3개의 접시위에 각각 몇 개씩 쌓여 있다. 단, 어느 접시에도 각 접시에는 가장 크기가 작은 컵이 아래에, 그 다음 작은 컵이 그 위에, 그 다음 .... 과 같이 컵의 크기 순으로 쌓여 있다.

다음 그림은 n=5인 경우에 각각 2개 0개 3개의 컵이 쌓여 있는 모습을 나타낸다.



이와 같이 컵의 초기 상태가 주어졌을 때, 다음의 규칙 1~3을 따르면서 모든 컵을 a또는 c의 접시로 모두 옮기는 것이 목적이다.

규칙은 다음과 같다.

규칙 1 - 1번에 1개의 컵만을 옮길 수 있다. 그리고 가장 위에 있는 컵만을 옮길 수 있다. 따라서 가장 큰 컵을 옮겨야 한다.

규칙 2 - 큰 컵 위에 작은 컵을 올려둘 수 없다.

규칙 3 - 컵 1개를 이동할 때, 바로 옆의 접시로만 이동해야 한다. 즉 a에서 c로나 c에서 a로 등은 바로 이동할 수 없다.

n개의 컵의 초기상태와 허용 횟수 m이 주어졌을 때, m회 이내의 이동으로 a또는 c로 모두 옮기는 것이 가능한지 판단하고, 가능한 경우에는 최소 횟수를 불가능한 경우에는 -1을 출력하는 프로그램을 작성하시오.

Input

첫 번째 줄에 n, m이 공백으로 구분되어 입력된다.

두 번째 줄에는 a접시에 있는 컵의 갯수와 각 컵의 크기가 공백으로 구분되어 입력된다.

세 번째 줄에는 b접시에 있는 컵의 갯수와 각 컵의 크기가 공백으로 구분되어 입력된다.

네 번째 줄에는 c접시에 있는 컵의 갯수와 각 컵의 크기가 공백으로 구분되어 입력된다.


[입력값의 정의역]
n <= 15
m <= 15,000,000

[Sub-Task Info]
#1 : n <= 10, m <= 10,000 (80%)
#2 : 추가제한조건은 없다. (20%)

Output

최소 횟수를 출력한다. m회 이내에 불가능할 경우에는 -1을 출력한다.

IO Example

입력
3 10
0
1 1
2 2 3

출력
9

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