#P6678. [COCI2019-2020#2] Popcount
[COCI2019-2020#2] Popcount
题目背景
Miniature Algebraic Natural Relay 是小型可编程设备的最新技术进步。 您可以使用 MalnarScript 为此设备编写自己的程序。
题目描述
程序要求如下:
- 程序的输入是一个严格小于 的单个非负整数。
- 程序的输出是一个严格小于 的单个非负整数。
- 使用 MalnarScript 进行编程时,您只能使用一个 位无符号整数变量 。在程序的开头,此变量保存输入,并且其在程序末尾的值被视为程序的输出。
- MalnarScript 的源代码最多必须包含 个格式为 的命令,这些命令按顺序执行,并且每个命令最多包含 个字符。
符号 的递归定义如下:
$$\texttt{换句话说,符号 可以是变量 ,也可以符合符号 的定义,或者在括号内表示二元表达式,其中每个操作数均符合相同的 定义。
上面定义中的符号 表示严格小于 的非负十进制整数。而符号 可以是 ,,,, 或 ,分别表示:加,减,按位或,按位与,左移和右移的运算。
此外,字符 在 符号中最多出现 次。
在执行加减运算时出现溢出或下溢时,MalnarScript 将以 为模执行这些运算。例如,当 时,在 MalnarScript 中,,。
每个命令中方程式的右侧求和为一个数字,然后将其存储到 中。为了计算右侧表达式,MalnarScript 首先将每次出现的 替换为其当前值。 然后,像在任何数学表达式中一样进行表达式的计算,即,括号优先。请注意,运算符的优先级(按照运算顺序)是不相关的,因为最终结果完全由括号的位置定义。
您的任务是编写一个程序,该程序在 MalnarScript 中输出程序,该程序以输入值的二进制表示形式计算一个数。
输入格式
第一行,两个正整数 ,含义见 题目描述。
输出格式
第一行中,您应该输出产生的 MalnarScript 程序的命令数。
在其余各行中,您应该输出所需程序的命令。每个命令必须在单独的行中输出,并且必须满足任务描述中所述的 MalnarScript 语法。
重要的是,输出中不要有不必要的空行或多余的空格字符。
每行(包括最后一行)必须以换行(\n
)结尾。
2 2
1
A=(A-((A&2)>>1))
3 5
2
A=((A&4)|((A&3)-((A&2)>>1)))
A=((A&3)+((A&4)>>2))
提示
数据范围及约定
Subtask | 分数 | 数据范围及约定 |
---|---|---|
, | ||
, | ||
, | ||
, |
说明
本题分值按 COCI 原题设置,满分 。
题目译自 COCI2019-2020 CONTEST #2 T4 Popcount。
感谢
另外,由于 testlib
库在洛谷环境下生成随机数在 时有问题,采用固定已生成随机数。部分测试点 较大,Special Judge 程序运行较久,如下。
特殊测试点编号 | 时限 |
---|---|
15 | 3s |
39 | 2s |
40 | 3s |
48 |
上述测试点时限仅用于 Special Judge 程序使用。