QOJ.ac

QOJ

Limite de temps : 1 s Limite de mémoire : 512 MB Points totaux : 110

#13433. Popcount

Statistiques

微型代数自然继电器(Miniature Algebraic Natural Relay,也称为 MALNAR)是微型可编程设备蓬勃发展领域的最新技术突破。你可以使用 MalnarScript 为该设备编写自己的程序,这是一种具有以下特性的奇特(esoteric)编程语言:

  • 程序的输入是一个严格小于 $2^N$ 的非负整数。
  • 程序的输出是一个严格小于 $2^N$ 的非负整数。
  • 在 MalnarScript 中编程时,你只能使用一个 $N$ 位无符号整数变量 $A$。在程序开始时,该变量保存输入值,程序结束时其值被视为程序的输出。
  • MalnarScript 的源代码必须由最多 $K$ 条形如 A=<expr> 的命令组成,这些命令按顺序执行,且每条命令必须由最多 $1000$ 个字符组成。符号 <expr> 递归定义如下:

    <expr> = A | <num> | (<expr><operator><expr>)

换句话说,符号 <expr> 既可以是一个变量 $A$,也可以符合符号 <num> 的定义,或者可以(在括号内)表示一个双目表达式,其中每个操作数都符合相同的 <expr> 定义。

上述定义中的符号 <num> 表示一个严格小于 $2^N$ 的非负十进制整数,而符号 <operator> 可以是 +-|&<<>>,它们(按顺序)分别表示加法、减法、按位或、按位与、左移和右移操作。

此外,字符 $A$ 在 <expr> 符号中最多只能出现 $5$ 次。

在进行加法和减法操作时,如果发生上溢(overflow)或下溢(underflow),MalnarScript 将对这些操作进行模 $2^N$ 的运算。例如,当 $N = 3$ 时,表达式 (7 + 3) 的计算结果为 $2$,而表达式 (2 - 5) 的计算结果在 MalnarScript 中为 $5$。

每条命令中等号右侧的表达式会计算出一个单一的数值,然后将其存储到 $A$ 中。为了计算右侧表达式的值,MalnarScript 首先将所有出现的 $A$ 替换为其当前值。然后,表达式的计算过程与任何数学表达式相同,即括号具有最高优先级。注意,运算符的优先级(就运算顺序而言)是无关紧要的,因为最终结果完全由括号的嵌套位置决定。

你的任务是编写一个程序,输出一个 MalnarScript 程序,该程序能够计算输入值二进制表示中 $1$ 的个数。

输入格式

第一行包含两个整数 $N$ 和 $K$,含义如题目描述所示。

输出格式

第一行应输出生成的 MalnarScript 程序的命令条数。

在接下来的各行中,你应该输出所求程序的命令。每条命令必须打印在单独的一行中,并且必须满足题目描述中 MalnarScript 的语法。

输出中不能有不必要的空行或多余的空格字符。每行(包括最后一行)必须以换行符('\n')结束。

子任务

子任务 分值 数据范围
1 15 $2 \le N \le 100$, $K = N - 1$
2 15 $N = 500$, $K = 128$
3 35 $1 \le N \le 40$, $K = 7$
4 45 $100 \le N \le 500$, $K = 10$

样例

输入样例 1

2 2

输出样例 1

1
A=(A-((A&2)>>1))

输入样例 2

3 5

输出样例 2

2
A=((A&4)|((A&3)-((A&2)>>1)))
A=((A&3)+((A&4)>>2))

说明

样例 1 说明

  • $\text{input} = 0 \Rightarrow \text{output} = (0 - ((0 \& 2) \gg 1)) = (0 - (0 \gg 1)) = (0 - 0) = 0$
  • $\text{input} = 1 \Rightarrow \text{output} = (1 - ((1 \& 2) \gg 1)) = (1 - (0 \gg 1)) = (1 - 0) = 1$
  • $\text{input} = 2 \Rightarrow \text{output} = (2 - ((2 \& 2) \gg 1)) = (2 - (2 \gg 1)) = (2 - 1) = 1$
  • $\text{input} = 3 \Rightarrow \text{output} = (3 - ((3 \& 2) \gg 1)) = (3 - (2 \gg 1)) = (3 - 1) = 2$

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.