맥주 캔 게임

맥주 캔 줄 게임은 한 명의 플레이어가 진행하는 게임이다. 플레이어의 목표는 주어진 맥주 캔과 나무 토큰의 배열을 최소 횟수의 이동으로 고쳐서 특정 조건을 만족하는 배열을 만드는 것이다.

맥주 캔 줄은 맥주 캔이나 나무 토큰으로 이루어진 일직선 행이다. 토큰마다 서로 다른 값을 가질 수 있으며, 값은 토큰에 적혀 있다. 각 줄의 시작과 끝은 분명하게 표시되어 있다.

게임 마스터가 평행한 맥주 캔 줄 두 개를 준비해 둔다. 줄은 보통 게임 마스터의 위치에서 어느 정도 떨어져 있으며, 이 배치 덕분에 게임 마스터가 진행 상황을 지켜볼 수 있다. 준비된 줄에 나타나는 모든 브랜드의 맥주 캔을 구할 수 있다. 줄에 나타나지 않는 다른 브랜드도 있을 수 있다. 모든 브랜드의 캔은 수량 제한 없이 제공되며, 모든 캔은 게임 마스터가 관리한다.

플레이어는 게임 마스터의 위치에서 출발해 준비된 맥주 캔 줄로 간다. 거기서부터 다음 세 가지 이동을 차례로 한다.

1. 캔 삽입 (Insert can). 플레이어는 게임 마스터에게 가서 원하는 브랜드의 캔을 받는다. 그 캔을 줄로 가져가 어떤 줄의 어느 위치에든 넣는다. 줄의 맨 앞이나 맨 뒤에 놓아도 된다.
2. 토큰 확장 (Expand token). 플레이어는 어떤 줄에서든 토큰 하나를 가져가 게임 마스터에게 준다. 게임 마스터는 토큰에 적힌 수만큼 캔으로 바꿔 준다. 플레이어는 캔의 브랜드를 자유롭게 섞어 고를 수 있다. 그다음 플레이어는 캔을 토큰이 나온 줄로 가져가서, 빠진 토큰의 자리에 원하는 순서대로 넣는다.
3. 캔 제거 (Remove can). 플레이어는 어떤 줄에서든 캔 하나를 골라 게임 마스터에게 가져가 근처의 쓰레기통에 버린다. 그 뒤 곧바로 줄로 돌아간다.

플레이어는 게임 내내 각 맥주 캔 줄을 일직선으로 가지런하게 유지해야 한다. 그래야 줄에 놓인 물건의 순서가 헷갈리지 않는다.

게임의 목표는 똑같은 맥주 캔 줄 두 개를 만드는 것이다. 두 줄이 같다는 것은 두 줄이 맥주 캔만 포함하고, 캔의 개수가 같으며, 1번째부터 줄 길이까지 모든 k에 대해 한 줄의 k번째 캔 브랜드가 다른 줄의 k번째 캔 브랜드와 같다는 뜻이다.

입력은 두 줄이며, 각각 처음의 두 맥주 캔 줄을 나타낸다. 각 줄에는 소문자 a부터 z까지와 숫자 0부터 9까지만 들어 있다. 소문자 한 글자는 맥주 캔 브랜드 하나를 나타내며, 서로 다른 글자는 서로 다른 브랜드를 뜻한다. 게임에서 쓸 수 있는 브랜드는 입력에 나타날 수도 있고 나타나지 않을 수도 있다. 숫자 한 글자는 토큰 하나를 나타내며, 토큰의 값은 그 숫자와 같다. 각 입력 줄은 소문자만 있거나 숫자만 있다.

첫 번째 줄은 최소 1자, 최대 10,000자이다. 두 번째 줄은 최소 1자, 최대 1,000자이다. 각 줄의 숫자는 100개를 넘지 않는다.

두 개의 똑같은 맥주 캔 줄을 얻는 데 필요한 최소 이동 횟수를 정수 하나로 출력한다.