멈출까, 멈추지 않을까

시간 제한1초메모리 제한512 MB

요약

32개의 1비트 레지스터와 초기값이 임의인 작은 어셈블리 프로그램에서 RANDOM 명령의 비결정성을 고려해 STOP까지 도달하는 최소 사이클 수를 구하거나 HANGS를 출력합니다.

난이도: 보통10점 중 6점
유형: BFS, 비트 연산, 시뮬레이션, 그래프
정답자: 아직 제출이 없습니다

문제

어린 톰(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를 출력한다.

예제2

예제 1
입력
```
5
SET 0 1
JZ 4 0
RANDOM 0
JMP 1
STOP
```
예상 출력
```
6
```

예제 2

입력

5
MOV 3 5
NOT 3
AND 3 5
JZ 0 3
STOP

예상 출력

HANGS