Problem L
Language Interpreter
When preparing for the CS3233 Final Team Contest, we (the problem setters) realized that one of the problems can be easily solved by using our custom programming language. Right after that realization, we decided to simply replace that problem with this one — write the interpreter for our programming language!
Our programming language is quite simple and was inspired by the assembly language. There are only 32 local variables (i.e., the registers), denoted by r0, r1, r2, …, r31.
The instructions are as follows ($0 \leq x, y, z \leq 31$; $0 \leq c \leq 2^{32}-1$). We denote the $(i+1)$-th register by r$i$.
-
add r$x$, r$y$, r$z$ — this instruction adds the value contained in register r$y$ and the value contained in register r$z$, and stores the result in register r$x$. In other words, $\texttt{r$x$} \gets \texttt{r$y$} + \texttt{r$z$}$. Note that it is possible that $x = y$, $x = z$, or $y = z$.
-
addi r$x$, r$y$, $c$ — this instruction adds the value contained in register r$y$ and the constant $c$, and stores the result in register r$x$. In other words, $\texttt{r$x$} \gets \texttt{r$y$} + c$. Note that it is possible that $x = y$.
-
move r$x$, r$y$ — this instruction copies the value contained in register r$y$ to register r$x$. In other words, $\texttt{r$x$} \gets \texttt{r$y$}$. Note that it is possible that $x = y$.
-
li r$x$, $c$ — this instruction sets the value of register r$x$ to $c$. In other words, $\texttt{r$x$} \gets c$. Note that $c$ is a constant.
-
for $c$ — this instruction starts a for-loop. The instructions inside the for-loop will be executed $c$ times. Note that $c$ is a constant.
-
rof — this instruction ends the innermost for-loop. It is guaranteed that there is an open for-loop when this instruction is encountered, and every opened for-loop will be closed by this instruction.
Furthermore, each register can only store integers in the range $[0, 2^{32}-1]$. If the result of an operation is outside this range, it will be wrapped around. In other words, every operation is performed modulo $2^{32}$.
Given the instructions in our programming language, your task is to execute the instructions and output the value of all registers after the execution.
Input
The first line contains two integers $n$ and $k$, denoting the number of instructions and the number of registers used in the program ($1 \leq n \leq 100$; $1 \leq k \leq 32$). The registers are numbered from r0 to r$(k-1)$.
The second line contains $k$ integers between $0$ and $2^{32}-1$ (inclusive), denoting the initial values of the first $k$ registers. The $(i+1)$-th integer is the initial value of register r$i$.
The next $n$ lines contain the instructions. All instructions are guaranteed to be valid and formatted as described above. The instructions are guaranteed to be well-formed, i.e., every for instruction will have a corresponding rof instruction. For each instruction, $0 \le x, y, z \le k-1$ and $0 \le c \le 2^{32}-1$.
Output
Output a line containing $k$ integers, denoting the value of the first $k$ registers after the program is executed. The $(i+1)$-th integer should be the value of register r$i$.
Explanation of Sample Input
The program in the sample is equivalent to the following Python program:
r0, r1, r2 = 1, 2, 3
r0 = r0 + r0
r0 = r1 + 1
r1 = 100
for i in range(2):
for j in range(3):
r2 = r0 + r1
r1 = r2
for j in range(4):
r2 = r0 + r2
r1 = r2
r0 = r0
r2 = 4234
r2 = (r2 + 4294966295) % (1 << 32)
print(r0, r1, r2)
| Sample Input 1 | Sample Output 1 |
|---|---|
16 3 1 2 3 add r0, r0, r0 addi r0, r1, 1 li r1, 100 for 2 for 3 add r2, r0, r1 move r1, r2 rof for 4 add r2, r0, r2 move r1, r2 move r0, r0 rof rof li r2, 4234 addi r2, r2, 4294966295 |
3 142 3233 |
