| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 114 | 60 | 59 | 53.636% |
로봇 천재 구름이는 연구의 일환으로 A-머신을 제작했다! A-머신은 긴 테이프에 적힌 기호들을 일정한 규칙에 따라 바꾸며 동작하는 기계로, 다음 네 부분으로 이루어져 있다.
테이프
$L$개의 칸이 일렬로 연결된 형태로, 각 칸에는 0 또는 1이 쓰여있다. 입력이 주어질 때 테이프는 공백 없이 연속된 문자열로 주어진다.
헤더
테이프 위의 칸 하나를 가리키고 있다. 초기 상태에는 테이프의 맨 앞 칸을 가리킨다.
현재 상태
머신의 상태를 나타낸다. 상태는 A부터 P까지 16개의 알파벳 대문자 중 하나이다.
행동표
$N$개의 규칙으로 이루어져 있다. 각 규칙은 (현재 상태, 읽은 문자, 덮어쓸 문자, 다음 상태, 이동할 방향) 5가지 변수로 이루어져 있다. (현재 상태, 읽은 문자)가 같은 서로 다른 규칙이 주어지지 않는다.
A-머신은 동작 방식은 다음과 같다.
1이라면 오른쪽으로, -1이라면 왼쪽으로 한 칸 움직이면 된다.구름이는 A-머신의 초기 상태, 테이프에 적힌 문자들의 초기 배열, 머신의 행동표가 주어졌을 때 A-머신이 정지하는지, 정지하지 않고 무한히 동작하는지를 판단하고자 한다. 구름이를 도와 A-머신의 정지 여부를 판단해 주자.
첫 번째 줄에 A-머신의 초기 상태가 주어진다.
두 번째 줄에 행동표의 규칙 개수 $N$과 테이프 길이 $L$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 32$; $1 \leq L \leq 15$)
세 번째 줄부터 $N$개의 줄에 걸쳐 A-머신의 현재 상태, 읽은 문자, 덮어쓸 문자, 다음 상태, 이동할 방향이 공백으로 구분되어 주어진다.
$N+3$ 번째 줄에 길이 $L$의 초기 테이프 문자열이 주어진다.
첫 번째 줄에 A-머신이 정지하면 STOP을, 정지하지 않으면 CONTINUE를 출력하라.
A 5 4 A 1 0 A 1 A 0 1 B 1 B 0 1 C -1 C 0 1 C 1 C 1 0 B 1 1001
STOP
주어진 A-머신의 행동표는 아래와 같다.
주어진 행동표를 바탕으로 A-머신은 아래와 같이 작동하게 된다. 값이 변하는 부분을 빨간색으로 표시하였다.
마지막 상태에서 헤더의 값이 B이고 테이프의 값은 1인데, 이는 행동표에서 찾을 수 없는 규칙이므로 A-머신은 정지하게 된다.
A 2 2 A 1 1 B 1 B 1 1 A -1 11
CONTINUE
School > GSHS x SASA > 제1회 GSHS x SASA 프로그래밍 경시대회 H번