Registers / 寄存器

题目描述

Klimi 有一台有故障的寄存器机器。每个寄存器中都存放着一个非负整数。

这台机器支持一种非常简单的程序语言。程序的每个非空行必须是下面几种形式之一。

1. 声明寄存器

registers <register_1> <register_2> ... <register_n>

声明程序中将会使用的普通寄存器。这条命令必须恰好出现一次，并且必须是程序的第一个非空、非注释行。

寄存器名可以是任意不含空白字符的 ASCII 字符串。X、Y、Out 是保留名称，不能在这一行中声明。你最多可以声明 $12$ 个普通寄存器。

注意：X、Y、Out 这三个特殊寄存器不需要声明，但可以像普通寄存器一样使用。

2. 自增

inc <register>

机器尝试将 <register> 的值增加 $1$。由于机器有故障，这次操作有 $50\%$ 的概率成功。若失败，则寄存器的值不变。

3. 自减

dec <register>

机器尝试将 <register> 的值减少 $1$。由于机器有故障，这次操作有 $50\%$ 的概率成功。若失败，则寄存器的值不变。

若寄存器原本的值为 $0$，即使操作成功，它的值也仍然保持为 $0$。

4. 条件跳转

jeq <register_1> <register_2> <label>

比较 <register_1> 与 <register_2> 的值。

如果二者相等，程序从标签 <label> 所在位置继续执行；否则继续执行下一条指令。

标签可以声明在当前指令之前，也可以声明在当前指令之后。

5. 标签

<label>:

声明一个标签，供 jeq 指令跳转使用。

标签名可以是任意不含空白字符的 ASCII 字符串。

6. 注释

# ...

若某一行的第一个非空白字符是 #，则这一整行被视为注释，执行时等价于空行。

除 jeq 指令造成的跳转外，程序按行顺序执行。当没有更多指令可以执行，也就是到达文件末尾时，程序结束。

你可以在程序中使用任意空白字符进行缩进或格式化，但换行仍然用于区分不同的程序行。

任务

请输出一份寄存器机器程序，使其能够计算两个数的乘积。

评测时，机器会提供三个特殊寄存器：

• X：初始值为 $X$；
• Y：初始值为 $Y$；
• Out：初始值为 $0$。

所有你声明的普通寄存器初始值也都是 $0$。

你的程序结束时，必须保证 Out 中的值恰好为：

$$X \times Y.$$

输入格式

本题在 Hydro OJ 中被转换为普通程序提交形式，但正式测试的标准输入为空。

你的提交程序不需要读取任何输入，只需要向标准输出打印一份符合上述语言规则的寄存器机器程序。

评测器会在隐藏测试中使用不同的 $X,Y$ 和随机种子运行你输出的寄存器机器程序。

输出格式

输出一份寄存器机器程序。第一条非空、非注释语句必须是 registers 声明。

数据范围

隐藏测试满足：

$$0 \le X,Y \le 1000.$$

子任务

子任务	附加限制	分值
1	$Y=1$	10
2	$Y=2$	20
3	$Y \le 30$	15
4	$30 \le X,Y \le 1000$	55

计分方式

记 $R$ 为程序执行过程中被计入的操作次数：

• 每条被执行的 jeq 指令一定计入 $1$ 次；
• inc 和 dec 只有在随机成功时才计入 $1$ 次；失败的 inc / dec 不计入 $R$。

若某次运行中 $R > 10^8$，则该测试点判为错误。

对于前三个子任务，只要在所有对应测试中都得到正确乘积且 $R \le 10^8$，即可得到该子任务满分。

对于第四个子任务，定义

$$T=\frac{R}{XY+X+Y+1}.$$

若 $T \le 13.5$，则该测试点得到满分比例 $1$。

若 $T>13.5$，则该测试点得分比例为

$$\max\left(\frac{15}{55},\ e^{-\left(\frac{T}{13.5}-1\right)^{0.75}}\right).$$

在 Hydro 配置中，四个子任务分别按原题测试点分组，组内取最小比例计分。

示例程序

下面这份程序不是正确的乘法程序，只用于展示语言格式。

# register with zero value
registers zero

# if X = Y jump to gotoInc
jeq X Y gotoInc

# terminate
jeq zero zero end

gotoInc:
inc Out

# label so we can jump to ending
end:

这份程序的行为是：

• 若 $X \ne Y$，程序总是结束并使 Out=0；
• 若 $X=Y$，程序会尝试执行一次 inc Out，所以有 $50\%$ 的概率使 Out=1，有 $50\%$ 的概率仍然使 Out=0。

本地调试说明

原包中提供了 interpreter.cpp，可用于本地测试你的寄存器机器程序。

其输入格式为：第一行输入两个整数 $X,Y$，从第二行开始输入寄存器机器程序源码，直到文件结束。

Hydro 正式评测时不使用这个输入格式；正式评测中，选手程序只需要输出寄存器机器程序源码。