영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
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 ySet register number y to the value x. ([y] = x)ADD x yAdd the value in register number x to register number y. ([y] = [y] + [x])SUB x ySubtract the value in register number x from register number y. ([y] = [y] - [x])JNZ x yJump 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 xRead the next byte from the DSP's input and store it in register number x.OUTPUT xSend the contents of register number x as output from the DSP.HALTTerminate 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
ADDinstruction will produce a sum greater than 255, and noSUBinstruction will produce a result less than 0. - The program will always terminate correctly by reaching a
HALTinstruction. 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
INPUTinstructions that need to be executed. - The program will never attempt to execute instructions other than numbers 0..N-1. That is,
JNZwill never jump to an instruction ≥ N, and instruction number N-1 will always be either aHALTinstruction or aJNZinstruction 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.
| Group | Points | Constraints |
|---|---|---|
| 1 | 40 | The JNZ instruction does not appear in the test data. |
| 2 | 60 | No 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