NPU 优化 - المسألة

Furiosa AI 正在开发一种 NPU（神经网络处理单元），旨在比现有的处理单元更快地进行人工智能模型的训练和推理。在通用处理单元上运行的程序通过使用各种运算符处理存储在主机（host）中的数据来计算所需的值。在本题中，我们将这一过程简化，并考虑以下环境：

主机拥有 $1\,000\,000$ 个数据存储空间，每个空间都有一个从 $0$ 到 $999\,999$ 的编号。
每个运算符接收一个或多个输入数据，并计算出一个输出数据。运算符也有一个 $0$ 到 $999\,999$ 之间的编号。
程序由以下 BNF（巴科斯范式）表示：

<number> ::= 0 | 1 | ... | 999999 <value> ::= <number> | <number>(<list>) <list> ::= <value> | <list>,<value>
程序计算一个值。也就是说，程序是一个对应于 <value> 的字符串。
<value> 的值计算如下：
- 如果 <value> 表示为 <number>，则它是程序开始前存储在主机 <number> 号空间中的数据。
- 如果 <value> 表示为 <number>(<list>)，则它是使用 <number> 号运算符，并将 <list> 中的 <value> 依次作为输入数据计算出的输出数据。
在一个程序中，同一个 <number> 不会出现多次。

Furiosa AI 开发的 NPU 虽然可以比通用处理单元更快地执行相同的程序，但需要一个编译器将程序重新编译为 NPU 使用的低级指令。由于程序的内存使用量和执行时间会根据编译方式的不同而改变，因此需要一个优化的编译器来高效地使用 NPU。

NPU 拥有一个可以存储 $M$ 个数据的内存，每个内存空间都有一个从 $0$ 到 $M-1$ 的编号。NPU 支持以下三种指令：

a >> b
- 将主机中 a 号数据复制到内存的 b 号空间。（$0 \le a < 1\,000\,000$；$0 \le b < M$）如果该空间已有数据，则覆盖。
a << b
- 将内存中 b 号数据复制到主机的 a 号空间。（$0 \le a < 1\,000\,000$；$0 \le b < M$）如果该空间已有数据，则覆盖。
o = w | m1 m2 ··· ml
- 使用 w 号运算符，将内存中地址为 $m_1, m_2, \dots, m_l$ 的值依次作为输入数据，并将输出数据存储在内存的 o 号空间中。
- 存储输出数据的空间必须与存储输入数据的空间不同。即 $o \neq m_i$ ($1 \le i \le l$)。

NPU 程序是上述指令的序列，执行程序时，组成程序的指令会按顺序执行。

程序的效率由多种因素决定，但如果使用的指令数量较少，则该程序很可能是高效的。给定一个对应于 <value> 的字符串，请将其转换为一个 NPU 程序，该程序通过尽可能少的指令计算出 <value> 的值并将其存储在 $0$ 号内存中。

第一行给出 NPU 的内存大小 $M$。（$1 \le M \le 1\,000\,000$）第二行给出需要计算的 <value> 对应的字符串。该字符串的长度不超过 $1\,000\,000$。

如果 NPU 内存不足导致无法编译程序，则输出 $-1$。如果可以编译程序，则第一行输出计算 <value> 所需的最少指令数。从下一行开始，按顺序逐行输出组成程序的指令。每条指令的所有标记（token）之间用一个空格隔开。如果存在多种可能的答案，输出其中任意一个即可。

7
71(72(41,42),73(43,44))

7
41 >> 3
42 >> 4
43 >> 5
44 >> 6
1 = 72 | 3 4
2 = 73 | 5 6
0 = 71 | 1 2

3
71(72(41,42),73(43,44))

9
43 >> 2
44 >> 0
1 = 73 | 2 0
59 << 1
41 >> 2
42 >> 0
1 = 72 | 2 0
59 >> 2
0 = 71 | 1 2

2
71(72(41,42),73(43,44))

-1

QOJ.ac