P2682 土豆田

    • 109通过
    • 524提交
  • 题目提供者 打杂的8
  • 评测方式 云端评测
  • 标签 Special Judge 提交答案
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

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

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

    题目描述

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

    单元的编号就是供电的顺序,每次按编号顺序从1号到n*m号遍历一遍。

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

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

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

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

    2、out 输出当前处理单元的key值。

    3、swap 交换该单元的key和tmp。

    4、add X 给key值加上X,X只能是一个常数或者tmp,下同。

    5、set X 把key值修改为X

    6、opp 对key值取相反数。

    7、rev 对key值按位取反。

    8、L X 左移key值X位。

    9、R X 右移key值X位。

    10、ge t u(d,l,r) 访问当前单元上(u)或下(d)、左(l)、右(r)的那个单元的key值并把它复制到本单元的tmp,位置规则按照前面的图片所示。

    11、or X 对key值按位或X

    12、and X 对key值按位与X

    13、xor X 对key值按位异或X

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

    15、if X0 如果此时X0(只能是key或者tmp)不等于0则在下一次供电执行该语句的下一条语句,否则跳过下一条语句,执行下下条(如果存在的话)。

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

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

    可以通过慢慢尝试熟悉操作,我们提供了check.exe,把你的土豆程序potato.out和你想测试的输入数据potato.in放到与check.exe同文件夹下,运行之后可以在report.txt中查看你的程序的详细运行情况(真的非常详细,提供了每一个周期之后程序的状态)。

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

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

    1、输入两个整数a,b,|a|,|b|<=10^9,输出-a+b,处理单元限制为1*3。 编号规则如图,没有必要全部使用,下同。

    2、输入一个整数 1<=|a|<=10^7,输出233*a,处理单元限制为2*2。

    3、输入一个整数a,1<=|a|<=10^9,输出a的绝对值,处理单元限制为2*2。

    4、输入128个整数a1……a128, 1<=|ai|<=2*10^6输出这些数的和,处理单元限制为4*2。

    5、输入两个整数a,b, 1<=|a|,|b|<=2.1*10^9,输出(a+b)/2 处理单元限制为2*2。

    6、输入一个整数0<=|a|<=2*10^9,输出a在计算机的32位二进制表示中1的数量,处理单元限制为2*2。

    7、输入两个整数a,b,0<=|a|,|b|<=2*10^9,输出a,b的较大值,处理单元限制为2*2

    8、输入一个整数1<=n<=42,有数列f(0)=1,f(1)=1,f(n)=f(n-1)+f(n-2),计算f(n),处理单元限制为3*3。

    输入输出格式

    输入格式:

    本题为提交答案题。

    输出格式:

    第一行为n和m,表示你用了n行m列

    接下来n*m个部分,第i个部分的第一行ti表示在第i个处理单元中命令的数量(可以为0),接下来ti行每行描述一个命令,见上文所述。

    输入输出样例

    输入样例#1: 复制
    例:一个使用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*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

    说明

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

    如果你的第i个任务的程序能得出正确的结果,并且和标准答案运行所需的周期数量相同或比其更少,得Pi分,否则设你的程序运行了a个周期,标准答案运行了s个周期,你的分数为 Pi*(s/a)*0.8向下取整(注意,部分正确显示WA,但是仍然有分数)。

    对于每个任务的Pi如下所示:

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

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

    比赛结束后我将公布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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。