디지털 신호 처리기

Anna-Maria는 풍력 발전기를 만들려고 하며, 풍력 발전기의 제어 시스템에 구성 요소로 사용할 새로운 종류의 처리기를 발명했다. 이 처리기는 디지털 신호를 처리하는 이른바 DSP, Digital Signal Processor이다. 실제로 이는 일련의 정수가 입력으로 DSP에 공급되면, 미리 프로그래밍된 소프트웨어에 따라 이를 처리하고 일련의 정수를 출력으로 생성한다는 뜻이다.

Anna-Maria는 자신을 위해 DSP을 생산할 공장에 주문을 넣었지만, 경제 위기로 인해 생산이 지연되고 있다. 이미 자신의 DSP을 위한 프로그램을 잔뜩 작성한 Anna-Maria는 조금 조급해져서 DSP들이 완성되자마자 자신의 프로그램이 정말 제대로 작동할지 확인하고 싶어 한다. 그래서 그녀는 DSP을 사용할 수 있게 되기 전에 프로그램을 시험할 수 있도록, DSP의 동작을 시뮬레이션하는 프로그램을 작성해 달라고 당신에게 부탁한다.

DSP의 동작을 정의하는 소프트웨어는 $0$부터 $N-1$까지 번호가 매겨진 $N$개(최대 256개)의 기계어 명령어(어셈블리 명령어라고도 한다)로 이루어진 수열이다. 명령어는 CONST, ADD, SUB, JNZ, INPUT, OUTPUT, HALT의 7종류가 있다. 각 명령어에는 0-2개의 매개변수가 있으며, 각 매개변수는 정수 $0..255$이다. 또한 DSP에는 각각 한 바이트(즉, 정수 $0..255$)를 저장하는 레지스터 256개로 구성된 작업 메모리가 있다.

프로그램은 DSP이 명령어 0을 실행하기 시작하고, 이어서 명령어 1 등을 차례로 실행하는 방식으로 동작하며, HALT 명령어가 실행되면 프로그램 실행이 종료된다. 실행을 시작할 때 모든 레지스터의 값은 0이다.

기계어 명령어는 다음과 같이 정의된다.

• [CONST x y] y번 레지스터의 값을 x로 설정한다. ([y] = x)

• [ADD x y] x번 레지스터의 값을 y번 레지스터에 더한다. ([y] = [y] + [x])

• [SUB x y] y번 레지스터의 값에서 x번 레지스터의 값을 뺀다. ([y] = [y] - [x])

• [JNZ x y] 0이 아니면 점프: x번 레지스터가 0이 아니면 y번 명령어로 ``점프''한다. 즉, y번 명령어를 다음에 실행할 명령어로 삼는다. 반대로 x번 레지스터가 0이면, JNZ 다음의 명령어부터 평소와 같이 실행을 계속한다.

• [INPUT x] DSP의 입력에서 다음 바이트를 읽어 x번 레지스터에 저장한다.

• [OUTPUT x] x번 레지스터의 내용을 DSP의 출력으로 보낸다.

• [HALT] 실행을 종료한다.

채점

제출한 해답은 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ | $40$ | 테스트 데이터에 JNZ 명령어가 등장하지 않는다.

$2$ | $60$ | 추가 제한이 없다.

입력은 DSP에서 실행할 프로그램과, 그 뒤에 DSP에 공급될 입력으로 구성된다.

첫째 줄에는 프로그램의 기계어 명령어 수를 나타내는 정수 $N$, $0<N<256$이 주어진다. 이어지는 $N$개의 줄에는 명령어가 주어진다. 각 명령어는 명령어의 이름과 그 뒤에 오는 명령어의 매개변수로 구성된다. 각 매개변수는 범위 $0..255$의 정수로 표현된다. 기계어 명령어가 주어지는 $N$개의 줄 다음에는 범위 $0..255$의 수들이 한 줄에 하나씩 주어진다. 이 수들은 DSP의 입력, 즉 DSP 프로그램의 INPUT 명령어들이 읽는 수열을 이룬다.

DSP 프로그램과 그 입력은 다음 조건을 만족한다고 가정할 수 있다.

• 어떤 ADD 명령어도 255보다 큰 합을 만들지 않으며, 어떤 SUB 명령어도 결과로 0보다 작은 수를 만들지 않는다.

• 프로그램은 항상 HALT 명령어에 도달하여 정상적으로 종료된다. 즉, 프로그램은 무한 루프에 빠지지 않는다.

• 실행해야 하는 명령어의 수는 백만 개를 초과하지 않는다.

• 실행해야 하는 모든 INPUT 명령어에 충분한 입력이 항상 주어진다.

• 프로그램은 절대로 $0..N-1$번 이외의 명령어를 실행하려고 하지 않는다. 즉, JNZ는 절대로 명령어 $\ge N$로 점프하지 않으며, $N-1$번 명령어는 항상 HALT 명령어이거나 앞에 있는 명령어로 점프하는 JNZ 명령어이다.

주어진 입력의 프로그램을 실행하는 DSP을 시뮬레이션하고 DSP의 출력을 출력한다. OUTPUT 명령어가 실행될 때마다, 해당 OUTPUT 명령어가 보낸 출력인 범위 $0..255$의 정수 하나를 한 줄에 출력한다.