UOJ Logo Universal Online Judge

UOJ

#116. 【ZJOI2015】黑客技术

附件下载 统计

最近傲娇少女幽香很忙,于是让跳蚤国王出了一道题给 ZJOI2015,一时间人人自危。你秘密潜伏了下来想窃取跳蚤国王的试题。

终于有一天,趁跳蚤国王出去练习跳高,你偷偷打开了跳蚤国王的电脑 —— 结果发现试题被 $10$ 个电子密码锁锁住了!

任何事情都阻挡不了你进省队的决心!每个电子密码锁内部有 $10$ 道检测工序,输入密码后,每通过一道检测工序密码锁就会输出一行 “ok”。如果输出了 $10$ 行 “ok” 那么就解开了该密码锁。

根据常识知,跳蚤国王一定是用高级计算机语言 flea++ 写代码的,然后用 flea++ 的编译器编译成汇编代码,再用汇编编译器编译为机器码。

显然你没有这 $10$ 个电子密码锁的 flea++ 源代码,通过反汇编,你获得了这 $10$ 个电子密码锁的汇编代码。

跳蚤的程序开始运行时会开出长度为 $2^{23}$ 的 $32$ 位有符号整数数组 $a$,元素分别为 $a_0, a_1, \dots, a_{2^{23} - 1}$,并全部初始化为 $0$。

在跳蚤的汇编语言中,有三种量:“@ $c$”,“\$ $c$”,“# $c$” (不含引号)。其中 $c$ 是个整数且 $c \in [-2^{31}, 2^{31})$。

  • @ $c$” 表示整数常量 $c$。
  • \$ $c$” 表示 $a_c$。
  • # $c$” 表示 $a_{a_c}$。

如果程序运行过程中试图访问的量会导致数组下标越界,那么就会产生 “Runtime Error” 错误并异常退出。

汇编代码由若干行组成,每行是一条语句(从 $1$ 开始编号),程序会从第 $1$ 条语句从上往下执行。

语句有下面这么几种:

  • 赋值语句:= $a$ $b$
    • $a, b$ 是某个量。
    • 表示把 $b$ 的值赋给 $a$。
    • 如果 $a$ 是个整数常量那么会产生 Runtime Error 错误并异常退出。
  • 输入语句:getc $c$geti $c$
    • $c$ 是某个量。
    • getc $c$ 表示读入一个字符,把该字符的 ASCII 码存入 $c$ 中。
    • geti $c$ 表示读到下一个非空白字符的位置,读入十进制表示的 $32$ 位有符号整数,存入 $c$ 中。(空白字符即 ASCII 码为 $9, 10, 13, 32$ 的字符)
    • 如果 $c$ 是个整数常量那么会产生 Runtime Error 错误并异常退出。如果读入整数失败则输出相关信息并异常退出。
  • 输出语句:putc $c$puti $c$
    • $c$ 是某个量。
    • putc $c$ 表示输出一个字符,$c$ 是该字符的 ASCII 码。
    • puti $c$ 表示输出整数 $c$ 的十进制表示。
  • 条件跳转语句:if $c$ $t$
    • $c, t$ 是某个量。
    • 表示如果 $c$ 不是 $0$,那么跳转到第 $t$ 条语句继续执行(即下一条要执行的语句变为第 $t$ 条语句);
    • 如果是 $0$,那么不进行任何操作,继续执行下一条语句。
  • 运算语句:$o$ $a$ $b$ $c$
    • $a, b, c$ 是某个量,$o$ 是某个运算符。
    • 该语句表示把 $a$ 和 $b$ 进行 $o$ 的运算,把结果赋值给 $c$。
    • 如果 $o$ 是 + 则表示加法,即 $a + b$。
    • 如果 $o$ 是 - 则表示减法,即 $a - b$。
    • 如果 $o$ 是 * 则表示乘法,即 $a \times b$。
    • 如果 $o$ 是 / 则表示做除法然后下取整,即 $\lfloor \frac{a}{b} \rfloor$。
    • 如果 $o$ 是 < 则表示 $a < b$ 则结果为 $1$,否则为 $0$。
    • 如果 $o$ 是 == 则表示 $a = b$ 则结果为 $1$,否则为 $0$。
    • 如果 $c$ 是个整数常量或者作除法时除数为 $0$ 那么会产生 Runtime Error 错误并异常退出。

程序运行过程中如果试图执行第 $-1$ 条语句那么程序正常结束,如果试图执行除此之外的不存在的语句那么会产生 Runtime Error 错误并异常退出。

如果执行的语句条数超过 $10^7$ 那么会产生 Time Limit Exceeded 错误并异常退出。

现在,是时候展现你卓越的黑客技术了!

输入格式

本题为提交答案题。所有输入数据 lock1.in~lock10.in 见数据下载。

每个输入文件表示一个密码锁的汇编代码。

我们还提供了一个来自跳蚤国的模拟器,能直接执行汇编代码。

在终端中先切换到该试题的目录下(Windows 选手请使用 cmd)。

然后在终端中运行:./run_linux64 <code>。其中 <code> 是你要执行的汇编代码的文件名。例如:./run lock1.in(当然我们也提供了对应的 32 位版本 run_linux32,Windows 选手请使用 run_win32 lock1.in

模拟器将从终端中读入数据。如果你想从文件中读入,请使用 < 来指定。

例如:./run lock1.in <lock1.out

其它操作系统请安装 node.js 然后使用 node run.js <code> 运行。

输出格式

针对给定的 $10$ 个输入文件 lock1.in~lock10.in,你需要分别给出你的输出文件 lock1.out~lock10.out

每个输出文件包含一些字符,表示你输入的密码。

样例一

input

= $ 4 @ 8388607
= # 4 @ -1
- $ 4 @ 1 $ 4
if @ 1 @ 5
= # 4 $ 5
- $ 4 @ 1 $ 4
= $ 5 $ 4
- $ 4 @ 1 $ 4
- $ 4 @ 1 $ 4
geti $ 0
= # 4 $ 0
- $ 4 @ 1 $ 4
+ $ 5 @ 0 $ 0
+ $ 4 @ 1 $ 4
= $ 1 # 4
= # 0 $ 1
+ $ 5 @ 0 $ 0
= # 4 $ 0
- $ 4 @ 1 $ 4
+ $ 4 @ 1 $ 4
= $ 1 # 4
== # 1 @ 666 $ 0
if $ 0 @ 25
if @ 1 @ 41
+ $ 5 @ -1 $ 0
= # 0 @ 0
if @ 1 @ 34
putc @ 111
putc @ 107
putc @ 10
+ $ 5 @ -1 $ 0
+ # 0 @ 1 # 0
- # 0 @ 1 $ 0
+ $ 5 @ -1 $ 0
= # 4 $ 0
- $ 4 @ 1 $ 4
+ $ 4 @ 1 $ 4
= $ 1 # 4
< # 1 @ 10 $ 0
if $ 0 @ 28
= $ 0 @ 0
+ $ 4 @ 2 $ 4
= $ 4 $ 5
+ $ 4 @ 1 $ 4
= $ 5 # 4
+ $ 4 @ 1 $ 4
if @ 1 # 4

output

666

explanation

该程序会读入一个整数,如果这个整数是 $666$ 那么就会输出 $10$ 行 “ok”。

评分方式

每个密码锁为一个测试点,每个测试点 $10$ 分。

对于每个密码锁,我们会以你的输出文件作为输入运行密码锁。

如果程序异常退出则该测试点 $0$ 分。

否则,我们会检查密码锁输出的每一行,设有 $x$ 行为 “ok”。如果 $x \geq 10$ 则该测试点满分,否则该测试点得 $x$ 分。

后记

你花了很长时间破解密码锁,最后也没有破解出来。最后硬着头皮去了 ZJOI2015,发现自己的事迹被写在了题面里。

备注

题目中提到的 “$32$ 位有符号整数” 等价于 C/C++ 中的 intPascal 中的 longint,能表示 $[-2^{31}, 2^{31})$ 以内的整数。

计算过程可能会溢出,比如:$2147483647 + 1 = -2147483648$,$100000 \times 100000 = 1410065408$。

下载

数据下载

请上传你要提交的文件,并命名为 lock1.out, lock2.out, lock3.out, lock4.out, lock5.out, lock6.out, lock7.out, lock8.out, lock9.out, lock10.out。如果你提交了 zip 压缩包,我们会为你自动解压。


或者通过如下表单上传: