#P2682. 土豆田

土豆田

题目背景

大宁在他家门口种了一大片土豆田,划分为 n×mn \times m 的地块。

大宁准备搭建学校的 OJ,为了测试土豆田的性能,大宁找到了你,为他的土豆编写代码。

题目描述

大宁的土豆田是以地块为单位的,每个地块里的所有土豆的集合称为一个处理单元,可以储存两个值:key(键值)和 tmp(缓存值),均为 3232 位带符号整数,每个单元。可以执行若干命令。大宁会骑着自行车轮流给每个处理单元供电,顺序如图,展示的是一个被分割为 4×44\times 4 处理单元的土豆田:

单元的编号就是供电的顺序,每次按编号顺序从 11 号到 n×mn\times m 号遍历一遍。

每一次完整的遍历称为一个周期。

只有一块地上的土豆得到供电,它们才会工作,执行命令,所有命令执行完之后大宁会停止供电。

对于每一个处理单元,命令格式如下:

  1. in 读取一个数,存放到该单元的 tmp\text{tmp} 中。(如果 tmp\text{tmp} 中有数,那么覆盖掉,以下的所有存放均如此)

  2. out 输出当前处理单元的 key\text{key} 值。

  3. swap 交换该单元的 key\text{key}tmp\text{tmp}

  4. add Xkey\text{key} 值加上 XXXX 只能是一个常数或者 tmp\text{tmp},下同。

  5. set Xkey\text{key} 值修改为 XX

  6. oppkey\text{key} 值取相反数。

  7. revkey\text{key} 值按位取反。

  8. L/R X 左/右移 key\text{key}XX 位。

  9. get u/d/l/r 将当前单元上(u)/下(d)/左(l)/右(r)面的单元的 key\text{key} 值并把它复制到本单元的 tmp\text{tmp},位置规则按照前面的图片所示。

  10. or/and/or Xkey\text{key} 值按位或/与/异或 XX

  11. wait 在本次供电的时间中等待,即什么事情也不做。

  12. if X 如果此时 X(只能是 key\text{key} 或者 tmp\text{tmp} )不等于 00 则在下一次供电执行该语句的下一条语句,否则跳过下一条语句,执行下下条(如果存在的话)。

  13. goto Y 下一次供电从第 YY 号命令开始执行,YY 只能是常数。

  14. end 强制结束所有的处理单元的命令,无视所有尚未执行的命令。

我们提供了 check.exe,把你的土豆程序 potato.out 和你想测试的输入数据 potato.in 放到与 check.exe 同文件夹下,运行之后可以在 report.txt 中查看你的程序的详细运行情况。

我们还提供了另一个样例土豆程序 example2.out,使用 2×22\times2 处理单元的土豆程序,内容为计算一个整数 aa1010 倍,可以自行解读(该样例并非该计算的最优解,只是为了展示命令)。

下面展示了一个 1×31 \times 3 的处理单元,所有单元不一定需要全部使用。

你有以下任务需要用编写土豆程序完成:

编号 输入 输出 数据范围 处理单元大小限制 分数 补充说明
11 aba\text{,}b bab-a ab109\lvert a\rvert \text{,}\lvert b\rvert \le10^9 1×31 \times 3 77
22 aa 233×a233\times a 1a1071 \le\lvert a\rvert \le10^7 2×22 \times 2 99
33 a\lvert a \rvert 1a1091 \le\lvert a\rvert \le10^9 1212 aa 的绝对值
44 128128 个整数 aia_i i=1128ai\sum^{128}_{i=1}a_i 1a2×1061 \le\lvert a\rvert \le2 \times 10^6 4×24 \times 2
55 aba\text{,}b a+b2\lfloor \frac{a+b}{2}\rfloor $\lvert a\rvert \text{,}\lvert b\rvert \le2.1\times10^9 $ 2×22 \times 2 1313
66 aa popcount(a)\operatorname{popcount}(a) a109\lvert a\rvert\le10^9 popcount(a)\operatorname{popcount}(a)表示 aa 在二进制表示下 11 的个数
77 aba\text{,}b max(a,b)\max {(a,b)} ab109\lvert a\rvert \text{,}\lvert b\rvert \le10^9 1414
88 nn f(n)f(n) 1n421 \le n \le 42 3×33 \times 3 2020 $f(n)=\begin{cases}1 & n<2\\f(n-1)+f(n-2) & n\ge 2\end{cases}$

输入格式

本题为提交答案题。

输出格式

第一行为 nnmm,表示你用了 nnmm 列。

接下来n×mn\times m个部分,第 ii 个部分的第一行 tit_i 表示在第 ii 个处理单元中命令的数量(可以为 00),接下来 tit_i 行每行描述一个命令,见上文所述。

例:一个使用1*1的土豆田处理单元(下称处理单元)的A+B problem
输入两个整数a,b,|a|,|b|<=10^9
输出a+b

1 1
5
in
swap
in
add tmp
out

解释:
第一行的1 1表示用的处理单元为1*1
第二行表示第一个处理单元有5条指令。
第三行的命令在第一个周期执行,读入了一个数(假定为a) ,此时该单元的状态为key=0,tmp=a
第四行在第二个周期执行,交换了key和tmp,状态为key=a,tmp=0
第五行在第三个周期执行,读入了另一个数b,状态为key=a,tmp=b
第六行在第四个周期执行,给key加上tmp,状态为key=a+b,tmp=b
第七行在第五个周期执行,输出该单元的key,即输出了a+b

提示

样例#1解释

这个样例实现了 A+B problem。

第一行的 1 1 表示用的处理单元为 1×11\times1

第二行表示第一个处理单元有 55 条指令。

第三行的命令在第一个周期执行,读入了一个数(假定为 aa) ,此时该单元的状态为 key=0,tmp=a\text{key}= 0 \text{,}\text{tmp}= a

第四行在第二个周期执行,交换了 key\text{key}tmp\text{tmp},状态为 key=a,tmp=0\text{key}= a \text{,}\text{tmp}= 0

第五行在第三个周期执行,读入了另一个数 bb,状态为 key=a,tmp=b\text{key}= a \text{,}\text{tmp}= b

第六行在第四个周期执行,给 key\text{key} 加上 tmp\text{tmp},状态为 key=a+b,tmp=b\text{key}= a+b \text{,}\text{tmp}= b

第七行在第五个周期执行,输出该单元的 key\text{key},即输出了 a+ba+b

如果你的程序在 20002000 个周期内没有运行完毕,或者有语法错误,或者超过处理单元尺寸限制,得 00 分。

如果你的第 ii 个任务的程序能得出正确的结果,并且和标准答案运行所需的周期数量相同或比其更少,得会得到该测试点的满分,否则设你的程序运行了 aa 个周期,标准答案运行了 ss 个周期,你的分数为 $\lfloor\text{该测试点分数}\times(\frac{s}{a})\times0.8 \rfloor$(注意,部分正确显示WA,但是仍然有分数)。

P1=7
P2=9
P3=12
P4=12
P5=13
P6=13
P7=14
P8=20

PS:如果你构造了什么好玩的土豆程序(可以和本题目中的任务无关),请到答疑博客下或者私信告诉我,会酌情给予奖励。

Check 下载见附件。

example2.out:

2 2 8 in add tmp
L 3 get r add tmp
get d add tmp
out 3 wait get l add tmp
3 wait get u add tmp