NPU 優化 - المسألة

Furiosa AI 正在開發一種 NPU（神經處理單元），其人工智慧模型的訓練與推論速度比傳統處理單元更快。在一般處理單元上運行的程式，會使用多種運算子來處理儲存在主機（host）中的資料，進而計算出所需的數值。在本題中，我們將此過程簡化，並考慮以下環境：

主機擁有可儲存 $1\,000\,000$ 個資料的空間，每個空間皆標記有從 $0$ 到 $999\,999$ 的編號。
每個運算子接收一個或多個輸入資料，並計算出一個輸出資料。運算子同樣標記有 $0$ 到 $999\,999$ 的編號。
程式以如下的 BNF（Backus-Naur Form）表示：

<number> ::= 0 | 1 | ... | 999999 <value> ::= <number> | <number>(<list>) <list> ::= <value> | <list>,<value>
程式計算一個值，即程式為對應 <value> 的字串。
<value> 的值計算方式如下：
- 若 <value> 表示為 <number>，則其值為程式開始前儲存在主機 <number> 號空間中的資料。
- 若 <value> 表示為 <number>(<list>)，則其值為將 <list> 中的 <value> 依序作為輸入資料，並使用 <number> 號運算子計算出的輸出資料。
在同一個程式中，相同的 <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
- 將記憶體中位址為 $m_1, m_2, \dots, m_l$ 的值依序作為輸入資料，執行 $w$ 號運算子，並將輸出資料儲存至記憶體的 $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