← 返回题目列表

Codeforces · 93/C

C. 阿泽姆布勒

中文机器翻译题面 查看原题

在搜索文本中的字符串的 Search Ultimate 程序失败后,Igor K. 开始思考:“到底为什么我的程序运行得这么慢?”当他仔细检查代码时,他说:“我的代码没有错误,但我知道我们将如何改进 Search Ultimate!”从书架上拿出一本大书。这本书是“Azembler. 主要是新方法”。

仔细翻阅这本书后,Igor K. 意识到,事实证明,你可以将数字相乘的速度提高数十倍。 “Search Ultimate 将比以往更快!” ——那家伙高兴地喊道,然后开始工作。

现在让我们澄清伊戈尔的想法是什么。问题是编译器生成的代码远非完美。标准乘法确实比书中提到的技巧慢。

Azembler 语言使用 26 个寄存器(eax、ebx、...、ezx)和两个命令进行操作:

- [x] — 返回位于地址 x 中的值。例如,[eax] 返回位于地址中的值,等于寄存器 eax 中的值。
- lea x, y — 分配给寄存器 x,表示为第一个操作数,第二个操作数的地址。因此,例如,“lea ebx,[eax]”命令将把 eax 寄存器的内容写入 ebx 寄存器:首先将完成 [eax] 操作,其结果将是位于 eax 中写入的地址中的某个值。但我们不需要这个值——下一个操作将是 lea,它将获取 [eax] 地址,即 eax 寄存器中的值,并将其写入 ebx。

乍一看,第二个操作似乎毫无意义,但事实证明,将操作写为是可以接受的

lea ecx, [eax + ebx],

lea ecx, [k*eax]

甚至

lea ecx, [ebx + k*eax],

其中 k = 1、2、4 或 8。

因此,寄存器 ecx 将相应地等于数字 eax + ebx、k*eax 和 ebx + k*eax。然而,这种运算的执行速度比通常的数字乘法要快几十倍。通过使用几个这样的运算,我们可以非常快速地将某个数字乘以另一个数字。当然,您可以使用任何寄存器来代替 eax、ebx 和 ecx。

例如,让 eax 寄存器包含一些我们应该乘以 41 的数字。这需要 2 行:

lea ebx, [eax + 4*eax] // 现在 ebx = 5*eax

lea eax, [eax + 8*ebx] // 现在 eax = eax + 8*ebx = 41*eax

Igor K. 对以下问题感兴趣:乘以给定数字 n 所需的最小 lea 运算次数是多少以及如何做到这一点?你的任务是帮助他。

考虑在初始时刻 eax 包含 Igor K. 即将乘以 n 的数字,并且从 ebx 到 ezx 的寄存器包含数字 0。在最后时刻,结果可以位于任何寄存器中。

输入

输入数据包含唯一的整数 n (1 ≤ n ≤ 255),Igor K. 即将乘以该整数。

输出

在第一行打印数字 p,它表示执行此操作所需的最小 lea 操作数。然后打印由 p 命令组成的程序,执行操作。保证对于 1 到 255 之间的任意 n 都存在这样的程序。

精确使用以下格式的命令(这里 k 等于 1、2、4 或 8,x、y 和 z 是任何寄存器,甚至是重合的寄存器):

lea x, [y]

lea x, [y + z]

lea x, [k*y]

lea x, [y + k*z]

请注意,命令末尾的多余空格是不可接受的。

示例

输入 #1

41

输出 #1

2
lea ebx, [eax + 4*eax]
lea ecx, [eax + 8*ebx]

输入 #2

2

输出 #2

1
lea ebx, [eax + eax]

输入 #3

4

输出 #3

1
lea ebx, [4*eax]