WEB 기계

Tim은 공을 정렬하는 기계, 즉 WEB 기계를 가지고 있습니다. WEB 기계에는 $n$개의 칸이 있는 바퀴가 있습니다. 각 칸에는 흰 공(W), 파란 공(B), 또는 빈 상태(E) 중 하나가 있을 수 있습니다. 바퀴 위의 특정 칸에는 헤드가 있어서 그 칸의 상태를 확인합니다. 헤드는 칸에 있는 공의 색을 판별할 수 있습니다. 또한 칸의 공을 집거나 칸에 공을 놓을 수 있습니다. 다만 헤드는 한 번에 공을 최대 하나만 들 수 있습니다. WEB 기계는 칸이 있는 바퀴를 시계 방향 또는 반시계 방향으로 돌릴 수 있습니다. 그림 1은 WEB 기계의 예입니다.

그림 1. WEB 기계의 예

WEB 기계는 제어 명령, 즉 WEB 명령에 따라 작동하며, WEB 명령의 순서열로 프로그램을 작성할 수 있습니다. WEB 명령의 종류와 뜻은 다음과 같습니다.

• Pick: 헤드 아래 현재 칸의 공을 집어 듭니다.
• Drop: 헤드가 들고 있는 공을 현재 칸에 놓습니다.
• Left: 바퀴를 시계 방향으로 한 칸 돌립니다.
• Right: 바퀴를 반시계 방향으로 한 칸 돌립니다.
• LeftStar $C$: 조건 $C$가 성립하는 동안 바퀴를 시계 방향으로 돌리고, 돌린 칸 수를 반환합니다.
• RightStar $C$: 조건 $C$가 성립하는 동안 바퀴를 반시계 방향으로 돌리고, 돌린 칸 수를 반환합니다.
• Jump $n$: 다음 $n$번째 명령으로 뛰어갑니다. ($n$이 $2$이면 다음 명령을 건너뛰고 그다음 명령을 실행합니다.)
• Jump $n$ if $C$: 조건 $C$가 성립하면 다음 $n$번째 명령으로 뛰어가고, 그렇지 않으면 아무것도 하지 않습니다.
• $X = E$: 식 $E$를 계산하여 그 값을 변수 $X$에 저장합니다.
• Stop: 기계를 멈춥니다.

Pick 또는 Drop을 실행할 때 조건이 맞지 않으면 기계는 아무 일도 하지 않습니다. 즉, Pick을 실행할 때 칸이 비어 있거나, Drop을 실행할 때 칸이 비어 있지 않은 경우입니다. 변수 $X$는 W, E, B를 제외한 대문자 알파벳이어야 합니다. LeftStar $C$, RightStar $C$, Jump $n$ if $C$의 조건 $C$는 W, E, B, 변수 $X$ 중 하나이거나, 이들의 부정형(!W, !E, !B, !$X$) 중 하나입니다. 조건 W는 헤드 아래 현재 칸의 공이 흰색이라는 뜻이고, B는 파란색, E는 칸이 비어 있다는 뜻입니다. 조건 $X$는 $X$가 0이 아닐 때($X \ne 0$) 성립합니다. 부정 조건은 원래 조건이 성립하지 않을 때 성립합니다. 예를 들어 !E는 E가 성립하지 않을 때 참입니다. 예를 들어 RightStar !E를 실행하면 헤드는 바퀴를 반시계 방향으로 돌리며 빈 칸을 찾습니다. 기계에 빈 칸이 하나라도 있으면 결국 헤드 아래에 빈 칸이 옵니다. 빈 칸이 하나도 없으면 이 명령은 무한 루프에 빠집니다.

무조건 점프(Jump $n$)와 조건부 점프(Jump $n$ if $C$)의 $n$은 음의 정수일 수도 있습니다. 예를 들어 Jump -1은 바로 앞 명령으로 분기합니다. Jump 0은 무한 루프를 일으키므로 실행하면 안 됩니다.

대입 명령 $X = E$는 정수 식 $E$를 계산하여 그 값을 변수 $X$에 저장합니다. 식의 값은 $-200$ 이상 $+200$ 이하여야 합니다($|E| \le 200$). 식에는 이전에 정의된 변수를 사용할 수 있습니다. 예를 들어 K가 미리 정의되어 있다면 K = K + 1은 K를 1 증가시킵니다. 정의되어 있지 않다면 오류입니다. 식 자리에 LeftStar 또는 RightStar 같은 별표 명령을 쓸 수도 있으며, 이때 대입은 돌린 칸 수를 대상 변수에 저장합니다. 예를 들어 다음 대입을 실행하면

X = RightStar B

그림 1 상태의 기계는 그림 2 상태가 되고, 변수 X의 값은 2가 됩니다.

그림 2. RightStar B를 실행한 후

또 다른 예로, 다음 코드는 그림 2 상태에서 그림 1 상태로 되돌립니다.

LeftStar !W
Right
Pick
Drop
Stop

세 번째와 네 번째 명령은 둘의 관계를 보이려고 넣은 것입니다. Pick과 Drop은 서로 역연산입니다.

식은 중첩할 수 없습니다. 즉, 이항 산술 연산자(+ 또는 -) 하나나 별표 명령 하나만 포함할 수 있습니다. 산술 연산자 중에서는 덧셈(+)과 뺄셈(-)만 쓸 수 있습니다. 곱셈, 나눗셈, 나머지 연산은 WEB 식에서 사용할 수 없습니다. 대입과 산술 연산자는 피연산자와 공백으로 구분해야 합니다. 정수 리터럴의 부호 바로 뒤에는 공백을 두면 안 됩니다. 예를 들어 -12는 유효하지만 - 12는 유효하지 않습니다.

Tim은 Stop으로 끝나는 WEB 명령 순서열인 WEB 프로그램으로 기계의 공을 정렬하려고 합니다. 처음에 공은 임의의 순서로 섞여 있지만 바퀴 위에서는 무리를 이루고 있습니다. Tim은 헤드 위치에서 시계 방향으로 읽었을 때, 흰 공 무리와 파란 공 무리가 빈 칸 무리로 나뉘어 있기를 원합니다. 시계 방향으로는 공 무리가 빈 칸 무리로 나뉘어 있지만, 바퀴 위에 있으므로 반시계 방향으로는 나뉘어 있지 않습니다. Tim을 도와 헤드 위치에서 시계 방향으로 읽었을 때 공이 W, E, B 순서로 정렬되도록 WEB 명령들을 작성해 주세요.

WEB 프로그램은 여러 줄로 이루어지며 각 줄에는 WEB 명령 하나만 들어갑니다. 따라서 위의 WEB 프로그램들은 유효하지만, 다음 프로그램은 구문 오류가 있어 유효하지 않습니다.

RightStar E X
= 10 + 2

대입문이 두 줄에 걸쳐 있기 때문입니다. 첫 번째 명령은 끝에 불필요한 변수가 있고, 두 번째 명령은 대입 대상 변수가 빠져 있습니다.

Tim이 원하는 대로 공을 정렬하는 WEB 프로그램을 작성하여 제출하세요. 프로그램은 WEB 기계의 초기 상태를 색깔별로 정렬된 공이 있는 최종 상태로 바꾸어야 하며, 반드시 Stop으로 끝나야 합니다. 초기 상태는 입력으로 주어지고, 최종 상태는 출력으로 주어집니다. 초기 상태에서 WEB 기계의 바퀴에는 빈 칸이 적어도 2개 있다고 가정합니다. 처음에 모든 빈 칸은 칸들 위에서 하나의 연속된 무리를 이루고 있습니다. 또한 기계에는 흰 공과 파란 공이 적어도 하나씩 있다고 가정합니다. 최종 상태에서는 흰 공과 파란 공이 빈 칸들의 무리로 나뉘어 있어야 하며, 칸을 시계 방향으로 읽을 때 가장 왼쪽에 있는 흰 공 위에 헤드가 있어야 합니다.