题目背景
有一天你在翻 OJ 时,发现了几道有趣的题。你还发现 OJ 上多出了一种语言—— HackVM。于是你打算用 HackVM 过掉这几道题。
题目描述
在 HackVM 语言中,一个字符就是一个操作,一个程序就是一个字符串。这个语言的程序从字符串的第一个字符开始运行,运行完毕后移动到下一个字符,直到运行至字符串尾或遇到了运行时错误而终止,或者执行了特定的终止程序的操作。为了防止死循环,若没有特殊规定,则最多执行 $10^7$ 次操作。另外,将当前运行到的位置称为 $PC$。这个语言拥有一个操作数栈,一个内存,一个调用栈,它们均以 long long
($64$ 位有符号整数)为单位,即一个基本块可以存放一个 long long
——所有的运算均是基于 long long
的(若你的运算过程中使用了超过 long long
的数,则不保证答案正确性,校验器可能会检测并报错)。其中内存有 $2097152$ 个基本块,从 $0$ 开始标号。
初始时,操作数栈、调用栈均为空,内存的所有块均初始化为 $0$。
操作描述
我们假设 $S_i$ 为该操作执行前操作数栈顶的第 $i+1$ 个块中的内容。
操作 | 描述 |
---|---|
' ' | 什么都不做(计算进代码长度) |
'p' | 弹出 $S_0$ 并将 $S_0$ 作为 `long long` 输出 |
'P' | 弹出 $S_0$ 并将 $S_0$ 作为字符输出 |
'r' | 输入一个整数并压入操作数栈 |
'R' | 输入一个字符并压入操作数栈 |
'0' | 将数字 $0$ 压入操作数栈 |
'1' | 将数字 $1$ 压入操作数栈 |
'2' | 将数字 $2$ 压入操作数栈 |
'3' | 将数字 $3$ 压入操作数栈 |
'4' | 将数字 $4$ 压入操作数栈 |
'5' | 将数字 $5$ 压入操作数栈 |
'6' | 将数字 $6$ 压入操作数栈 |
'7' | 将数字 $7$ 压入操作数栈 |
'8' | 将数字 $8$ 压入操作数栈 |
'9' | 将数字 $9$ 压入操作数栈 |
'+' | 弹出 $S_0,S_1$ 并将 $S_1+S_0$ 压入操作数栈 |
'-' | 弹出 $S_0,S_1$ 并将 $S_1-S_0$ 压入操作数栈 |
'\*' | 弹出 $S_0,S_1$ 并将 $S_1*S_0$ 压入操作数栈 |
'/' | 弹出 $S_0,S_1$ 并将 $S_1/S_0$ 压入操作数栈 |
':' | 弹出 $S_0,S_1$,若 $S_1<S_0$ 则压入 $-1$,若 $S_1=S_0$ 则压入 $0$,若 $S_1>S_0$ 则压入 $1$ |
'g' | 弹出 $S_0$ 并将 $PC$ 加上 $S_0$ |
'?' | 弹出 $S_0,S_1$,若 $S_1=0$ 则将 $PC$ 加上 $S_0$ |
'c' | 将当前 $PC$ 压入调用栈,弹出 $S_0$ 并将 $PC$ 设为 $S_0$ |
'$' | 将 $PC$ 设为调用栈栈顶,并将调用栈弹栈 |
'<' | 弹出 $S_0$ 并将标号为 $S_0$ 的内存中的内容压入操作数栈 |
'>' | 弹出 $S_0,S_1$ 并将 $S_1$ 存在标号为 $S_0$ 的内存中 |
'^' | 弹出 $S_0$ 后,将 $S_{S_0+1}$ 压入操作数栈(如代码段 0^ 会将之前的 $S_0$ 复制一份) |
'v' | 弹出 $S_0$ 与 $S_{S_0+1}$ 后将后者重新压入操作数栈(如代码段 1v 会将之前的 $S_0$ 与 $S_1$ 交换) |
'd' | 弹出 $S_0$ |
'!' | 终止程序 |
样例、具体实现以及可执行代码可以参考解释器 hackvm.cpp。
任务
测试点 1(3 分)
输入两个整数 $a,b$,输出 $a+b$。
测试点 2(5 分)
输入两个正整数 $a,b$,输出 $a\mod b$。
测试点 3(8 分)
输入三个整数 $a,b,c(1\le a,b,c< 2^{31})$,输出 $a^b\mod c$。
测试点 4、5(各 7 分)
第一行给出一个奇数 $n(1\le n\le 100)$。
接下来给出 $n$ 个整数。
输出这 $n$ 个数的中位数。
测试点 6、7(各 9 分)
给一个无向图,求 $1$ 号点到每个点的最短路。
第一行给出 $n,m(1\le n\le 40,1\le m\le 500)$,表示点数和边数。
接下来 $m$ 行,每行三个整数 $u,v,w$,表示 $u$ 到 $v$ 有一条权值为 $w$($0\le w\le 10^9$)的边。
输出 $1$ 号点到每个点的最短路之和(结果可能会超过 int
)。
保证没有重边和自环,点从 $1$ 开始标号。
测试点 8、9(各 13 分)
给一个有向图,求强联通分量个数。
第一行给出 $n,m(1\le n\le 100,1\le m\le 3000)$,表示点数和边数。
接下来 $m$ 行,每行两个整数 $u,v$,表示 $u$ 到 $v$ 有一条边。
输出答案。
保证没有重边和自环,点从 $1$ 开始标号。
测试点 10(12 分)
你需要输出程序本身(即实现一个 Quine 程序)。
注意代码长度不能为 0。
测试点 11(14 分)
给一段 HackVM 代码,你需要运行这段代码并输出其结果。
保证没有 r
R
P
操作,且 p
只会调用一次。保证会调用 !
退出。
保证这段程序使用的操作数不高于 60000 且内存使用不多于 65536,没有行末换行,你需要读到 EOF(-1)为止。
提示
你的程序应在对应的 data*.out
中,其中 *
是对应的测试点编号,每一个程序应仅有一行,程序及输出的结尾不应有换行或者多余的空格(空格虽然为空操作,但会被计入代码长度)。
对于测试点 10 以外的测试点,你不能使用 P
操作(只需要输出一个整数);而对于测试点 10,你不能使用 p
操作,且你的输出不能包含多余的换行符或空格。
所有程序的代码长度应该在 1B 到 50KB 之间。保证所有输入的数都在 int
范围内。每个测试点均只包含一组数据。上面写在一起的测试点,并没有捆绑。
下载
这个解释器,无疑是善良的出题人无私的馈赠。这个解释器涵盖了 Hackvm 中所有操作的实现。你可以利用这个解释器,对自己的程序进行全面的检查。足量的操作组数和多种多样的错误提示,能让程序中的错误无处遁形。出题人相信,这个美妙的解释器,可以给拼搏于 AC 这道题的逐梦之路上的你,提供一个有力的援助。