【自主出题】Mini-Machine & The Loop
题目 Mini-Machine & The Loop
题目背景
1936年，艾伦·图灵提出了图灵机的理论模型。一台图灵机由一条无限长的纸带、一个能够读写符号并改变状态的控制器组成。尽管结构如此简单，它却能够执行任何机械可计算的过程，为现代计算机科学奠定了基础。今天的计算机虽然复杂得多，其核心依然遵循着冯·诺依曼体系结构：存储程序，顺序执行。
题目描述
小明设计了一台迷你虚拟机，该机器包含 4 个 64 位有符号整数寄存器，名称分别为 r0, r1, r2, r3。
虚拟机能够执行一个由若干指令组成的程序。初始时所有寄存器的值均为 0，程序从第 1 行开始顺序执行，直到遇到 HLT 指令时停机。
虚拟机支持的指令集如下（每行一条指令，操作数之间用单个空格分隔）：
| 指令格式 | 含义 |
|---|---|
MOV dst, src |
将源操作数 src 的值复制到目标寄存器 dst。dst 必须是寄存器名；src 可以是寄存器名或整数常量（如 123、-5）。 |
ADD dst, src |
dst = dst + src。src 可以是寄存器名或整数常量。 |
SUB dst, src |
dst = dst - src。src 可以是寄存器名或整数常量。 |
JMP offset |
无条件跳转到“当前行号 + offset”的位置。offset 是一个整数。行号从 1 开始计数。 |
JNZ reg, offset |
若寄存器 reg 的当前值 不为 0，则跳转到“当前行号 + offset”；否则顺序执行下一条。 |
HLT |
停机，虚拟机立即退出。 |
程序结构保证：
- 程序有且仅有一条跳转指令，是一条
JNZ，且它的offset为负数（即往回跳），从而形成一个唯一的循环。 - 这个
JNZ所在的循环体内部没有任何其它跳转指令。也就是说，循环体由若干条纯算术指令（MOV、ADD、SUB）组成，最后紧跟着一条JNZ。 - 循环之前可能有一段顺序执行的“前缀”指令（也可以为空）；在
JNZ之后只有一条HLT指令，后面没有任何指令。 - 程序保证会最终停机（循环一定会终止）。
- 所有寄存器值、常数以及中间结果均在 $[-10^{18},10^{18}]$ 范围内，最终答案也保证在此范围内。
现在，给你一段符合上述约束的程序，请你输出虚拟机停机时 r0, r1, r2, r3 的值。
输入格式
第一行一个整数 M，表示指令的总行数。
接下来 M 行，每行一条指令，格式如上所述。行首行尾没有多余空格，操作数之间用单个空格隔开。
输出格式
一行四个整数，依次为寄存器 r0, r1, r2, r3 的值，之间用空格分隔。
样例输入 1
1 | 6 |
样例输出 1
1 | 0 15 0 0 |
解释
前缀指令将 r0 置为 5，r1 置为 0。
循环体为第 3～5 行：
ADD r1, r0→r1 += r0SUB r0, 1→r0 -= 1JNZ r0, -2→ 若r0 != 0则跳回第 3 行
该循环执行 5 次：r1 依次累加 5, 4, 3, 2, 1，总和为 15；r0 最终变为 0，退出循环，执行 HLT。
样例输入 2
1 | 5 |
样例输出 2
1 | 0 3000000000 0 0 |
数据范围与提示
- 对于 30% 的测试数据，循环实际执行次数 ≤ 1000。
- 对于 100% 的测试数据，1 ≤
M≤ 2000，循环执行次数可能高达 $10^{12}$。所有数值在 64 位有符号整数范围内。