cho.sh멈출까, 멈추지 않을까
시간 제한1초메모리 제한512 MB문제
어린 톰(Tom)은 프로그래밍을 배우고 있다. 방금 몇 개의 프로그램을 작성했지만, 그 프로그램이 언젠가 멈출지 알 수 없어 실행하기를 두려워한다. 톰을 도와주자.
이 문제는 보기보다 어렵다. 톰의 프로그램은 비결정적으로 동작할 수 있기 때문이다.
톰의 프로그램이 하나 주어질 때, 그 프로그램이 멈출 수 있는지 판정하고, 멈출 수 있다면 멈출 때까지 걸리는 가장 짧은 시간을 구하라.
톰의 컴퓨터에는 0번부터 31번까지 번호가 매겨진 32개의 1비트 레지스터가 있고, 프로그램은 0번부터 n − 1번까지 번호가 매겨진 n개의 명령어로 이루어진다.
아래에서 MEM[a]는 a번 레지스터의 값을 뜻하며, 0 ≤ a, b < 32, 0 ≤ x < n, 0 ≤ c ≤ 1이다.
명령어 집합은 다음과 같다.
| 명령어 | 의미 |
|---|---|
AND a b | MEM[a] := MEM[a] and MEM[b] |
OR a b | MEM[a] := MEM[a] or MEM[b] |
XOR a b | MEM[a] := MEM[a] xor MEM[b] |
NOT a | MEM[a] := not MEM[a] |
MOV a b | MEM[a] := MEM[b] |
SET a c | MEM[a] := c |
RANDOM a | MEM[a] := 무작위 값 (0 또는 1) |
JMP x | x번 명령어로 분기한다 |
JZ x a | MEM[a] = 0이면 x번 명령어로 분기한다 |
STOP | 프로그램을 멈춘다 |
모든 프로그램의 마지막 명령어는 항상 STOP이다(프로그램 안에 STOP이 여러 개 있을 수도 있다). 모든 프로그램은 0번 명령어에서 시작한다. 실행이 시작되기 전 레지스터에는 임의의 값이 들어 있을 수 있다. 각 명령어(STOP 포함)는 한 프로세서 사이클을 소모한다.
RANDOM 명령어와 임의의 초기 레지스터 값 때문에 하나의 프로그램이라도 여러 가지 방식으로 실행될 수 있다. 멈추는 모든 실행 중에서 사이클 수가 가장 작은 값을 구하면 된다. 만약 어떤 방식으로 실행해도 결코 멈추지 않는다면, 그 프로그램은 무한히 도는 것이다.
다음을 수행하는 프로그램을 작성하라.
- 톰의 프로그램을 입력받는다,
- 가장 짧은 실행 시간을 계산한다,
- 그 결과를 출력한다.
입력
첫째 줄에 명령어의 개수인 정수 n (1 ≤ n ≤ 16)이 주어진다. 다음 n개의 줄에는 각각 위 형식에 맞는 명령어가 하나씩 주어진다. 프로그램에서 공백 문자는 한 명령어를 이루는 토큰들 사이의 단일 공백뿐이다.
출력
첫째 줄에 프로세서 사이클로 측정한, 가능한 가장 짧은 실행 시간을 출력한다. 프로그램이 결코 멈출 수 없다면 대신 HANGS를 출력한다.