루미 알고리즘

#1294골드Digital Signal Processors

PO 2009 온라인 예선코딩영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Anna-Maria is planning to build a wind turbine, and has invented a new type of processor that she intends to use as a component in the turbine's control system. The processor is a so-called DSP, Digital Signal Processor, which processes digital signals. In practice, this means the DSP is fed a series of integers as input, processes them according to the programmed software, and produces a series of integers as output.

Anna-Maria has sent an order to a factory that will produce the DSP for her, but due to the economic crisis, production is taking longer than expected. Anna-Maria, who has already written lots of programs for her DSP, is getting a bit impatient and wants to make sure her programs will work right away when the DSPs are ready. She therefore asks you to write a program that simulates the DSP's behavior, so she can test her programs before the DSP is available.

The software that defines the DSP's behavior consists of a sequence of N (up to 255) machine instructions (also called assembly instructions), numbered from 0 to N-1. There are 7 types of instructions: CONST, ADD, SUB, JNZ, INPUT, OUTPUT, and HALT. Each instruction has 0–2 parameters, each of which is an integer 0..255. The DSP also has a working memory consisting of 256 registers, each containing a byte (i.e., an integer 0..255).

A program is executed by the DSP starting with instruction 0, then instruction 1, and so on, until a HALT instruction is executed, at which point the program terminates. When execution begins, all registers have the value 0.

The machine instructions are defined as follows:

  • CONST x y Set register number y to the value x. ([y] = x)
  • ADD x y Add the value in register number x to register number y. ([y] = [y] + [x])
  • SUB x y Subtract the value in register number x from register number y. ([y] = [y] - [x])
  • JNZ x y Jump if Not Zero: If register number x is not 0, “jump” to instruction number y, i.e., let instruction y be the next instruction to execute. If register number x is 0, continue execution as usual with the instruction after JNZ.
  • INPUT x Read the next byte from the DSP's input and store it in register number x.
  • OUTPUT x Send the contents of register number x as output from the DSP.
  • HALT Terminate execution.

Input

The input consists of the program to be run on the DSP, followed by the input data the DSP will be fed.

The first line contains an integer N, (1 ≤ N ≤ 255), the number of machine instructions in the program.

Then follow N lines with instructions. Each instruction consists of the instruction name, followed by the instruction's parameters. Each parameter is described by an integer in the range 0..255.

After the N lines of machine instructions, a number of integers in the range 0..255 follow, one per line. These constitute the input to the DSP, i.e., the series of numbers that the DSP program's INPUT instructions read from.

You may assume that the DSP program and its input satisfy the following:

  • No ADD instruction will produce a sum greater than 255, and no SUB instruction will produce a result less than 0.
  • The program will always terminate correctly by reaching a HALT instruction. That is, the program will not get stuck in an infinite loop.
  • The number of instructions that need to be executed will not exceed one hundred thousand.
  • There will always be enough input data for all INPUT instructions that need to be executed.
  • The program will never attempt to execute instructions other than numbers 0..N-1. That is, JNZ will never jump to an instruction ≥ N, and instruction number N-1 will always be either a HALT instruction or a JNZ instruction that jumps to an earlier instruction.

Output

Your program should simulate the DSP's execution of the program given in the input, and output the DSP's output: For each execution of an OUTPUT instruction, your program should output a line with an integer in the range 0..255, the output sent from the OUTPUT instruction.

Scoring

Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group.

GroupPointsConstraints
140The JNZ instruction does not appear in the test data.
260No additional constraints.

예제

예제 1

입력
15
INPUT 4
JNZ 4 3
HALT
INPUT 0
INPUT 1
CONST 0 2
JNZ 0 11
OUTPUT 2
CONST 1 0
SUB 0 4
JNZ 0 1
ADD 1 2
CONST 1 3
SUB 3 0
JNZ 3 6
5
1
1
2
2
3
3
4
4
5
6
출력
1
4
9
16
30

출처 표기

출처: Programmeringsolympiaden 2009년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.