만칼라

[p]

예제 1

Mancala는 아프리카에서 유래한 아주 오래된 게임으로, 이 문제에서는 그 원리를 빌려 사용한다. 위 그림은 5개의 배치를 보여 준다. 각 배치에는 5개의 그릇이 있으며, 그 안에는 다양한 수의 씨앗이 들어 있다. 가장 왼쪽에는 시작 배치의 예가 있고, 가장 오른쪽에는 원하는 최종 배치의 예가 있다. 최종 배치에 도달하려면 4번의 이동이 필요하다.

한 번의 이동은 다음 단계로 이루어진다:

• 그릇 하나를 선택하고 그 안에 있는 모든 씨앗을 꺼낸다.

• 시계 방향 또는 반시계 방향 중 한 방향을 선택한다.

• 먼저 방금 비운 그릇에 씨앗 하나를 뿌린다. 그런 다음 씨앗이 남아 있는 동안 선택한 방향을 따라 각 그릇에 씨앗을 하나씩 뿌린다.

원하는 최종 배치에 도달할 때까지 1-3의 단계들을 반복한다.

그림의 예제에서는 다음과 같이 이동한다. 먼저 그릇 B를 선택하고 반시계 방향으로 씨앗을 뿌린다. 다음 이동에서는 그릇 C를 선택하고 다시 반시계 방향으로 씨앗을 뿌린다. 세 번째 이동에서는 그릇 D와 반시계 방향을 선택한다. 네 번째이자 마지막 이동에서는 그릇 E에서 씨앗을 꺼낸다. 이제 어느 방향을 선택하더라도 결과는 같다. 따라서 시작 배치 1, 2, 3, 4, 5에서 네 번의 이동으로 최종 배치 5, 4, 3, 2, 1에 도달했다(그릇의 내용물은 A, B, C, D, E 순서로 제시된다).

시작 배치와 최종 배치를 입력받아 목표에 도달하는 데 필요한 최소 이동 횟수를 구하는 프로그램을 작성한다. 테스트에서는 6번보다 많은 이동이 필요한 경우가 절대 없다.

시작 배치에서 한 그릇에 들어 있는 씨앗 수의 최댓값은 10이다.

입력은 두 줄로 이루어진다. 첫째 줄에는 시작 배치가 그릇에 들어 있는 씨앗 수를 나타내는 공백으로 구분된 5개의 정수로 주어진다(순서는 A, B, C, D, E이다). 둘째 줄에는 최종 배치가 같은 방식으로 주어진다. 어떤 그릇도 10개보다 많은 씨앗을 포함하지 않는다.

최종 배치에 도달하는 데 필요한 최소 이동 횟수를 나타내는 정수 하나를 출력한다.