JOI 2005/2006 예선 4- 컵 쌓기(Stacking Cup) > 문제은행 : 정보올림피아드&알고리즘




2516 : 컵 쌓기(Stacking Cup)

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
23 회   
시도횟수
91 회   

문제

다양한 크기의 컵 n개와 A, B, C 3개의 쟁반이 있다. 

처음에 컵들이 쟁반에 거꾸로 쌓여있는데, 

각 쟁반에 있는 컵은 가장 작은 컵이 아래에 있고, 

그다음 두 번째로 작은 것, 

그다음 세 번째로 작은 것 등..

 

예를 들어, 그림 1은 n=5 이고 2개의 컵은 쟁반 A에, B에는 아무것도 없고, C에는 3개가 있다.

 

 

  

 

처음 쟁반의 상태가 주어지면, 모든 컵들을 이동하여 쟁반 A나 C에 쌓을 수 있다.

 

컵을 이동할 때는 다음의 세 가지 규칙을 따른다.

규칙 1. 쟁반의 컵은 가장 위에 있는 컵만 다른 쟁반의 가장 위에 있는 컵 위에 쌓을 수 있다.

규칙 2. 큰 컵 위에 작은 컵은 쌓을 수 없다.

규칙 3. A에서 C, C에서 A로는 직접 이동할 수 없다.
        따라서 직접 이동 가능한 것은 A에서 B, B에서 A, B에서 C, C에서 B 중 하나이다.

 

당신이 할 일은 N개의 컵과 정수 M이 주어질 때 쟁반 A에 M번 안에 모든 컵들을 쌓을 수 있는지를 결정하는 것이다.

가능하다면 최소 이동 횟수를 출력하고, 그렇지 않으면 -1을 출력한다.

 


입력형식

입력의 첫 번째 줄에는 컵의 개수 N(1≤N≤15)과, 이동가능횟수 M(1≤M≤15,000,000)이 공백으로 구분하여 입력된다. 그 다음 줄부터 4번째 줄까지 쟁반 A, B, C의 현재 상태가 들어오는데 각 줄의 첫 번째 값은 컵의 개수 k이고 두 번째부터 k개의 컵이 오름차순 정렬로 들어온다.


출력형식

출력은 한 줄로 이루어지는데 M번 안에 쟁반 A에 모든 컵을 쌓을 수 있다면 그 최소 횟수를 출력하고 불가능하면 -1을 출력한다.


입력 예

3 10
0
1 1
2 2 3

출력 예

9

입력 예

4 20
2 1 2
1 3
1 4

출력 예

3

입력 예

2 5
2 1 2
0
0

출력 예

0

입력 예

3 3
0
1 1
2 2 3

출력 예

-1


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP