Description

“哈佛架构”一词适用于指令和数据具有物理上分开的存储器的计算机。该术语起源于哈佛 Mark I 计算机，由 IBM 于 1944 年交付，该计算机使用纸带作为指令，使用继电器作为数据。

一些现代微控制器使用哈佛架构——但不使用纸带和继电器！数据存储器被组织成多个存储区（bank），每个存储区包含相同数量的数据项。每条引用数据的指令都有一个字节偏移量 $f$ 和一个位 $a$，用于选择要引用的存储区。如果 $a$ 为 $0$，则引用存储区 $0$。如果 $a$ 为 $1$，则在存储区选择寄存器（BSR）中的值标识要使用的存储区。假设每条指令执行时间相同，并且存在可以设置 BSR 值的指令。

例如，假设有 $4$ 个存储区，每个存储区有 $8$ 个字节。要访问位置 $5$，可以使用 $a = 0$ 和 $f = 5$ 的单条指令，或者在一条指令中将 BSR 设置为 $0$，然后使用 $a = 1$ 和 $f = 5$ 的指令。第一种方法更快，因为它不需要设置 BSR。

现在假设（使用相同的存储器）要访问的位置是 $20$。这里只能使用一种方法：执行一条指令将 BSR 设置为 $2$（除非 BSR 已经是 $2$），然后使用 $a = 1$ 和 $f = 4$ 的指令。

程序是操作的序列。每个操作可以是

• 变量引用，写作 V$i$，其中 $i$ 是正整数，或
• 重复，写作 R$n$ <program> E，其中 $n$ 是正整数，<program> 是任意程序。此操作相当于 <program> 的 n 次连续出现。

你的任务是确定程序的最小运行时间。具体来说，给定内存存储区的数量和大小以及要执行的程序，找出必须执行的最小指令数（引用内存位置和可能设置 BSR），以运行程序。为此，你必须确定将变量映射到存储区的方式，以产生最小的执行时间，并报告该执行时间——即完成程序所需的内存引用和 BSR 寄存器设置的数量。BSR 的值最初未定义，仅在指令显式设置其值时更改。

Input Format

输入包含一个测试用例。测试用例包含两行。第一行包含两个整数 $b$ 和 $s$，其中 $1 \leq b \leq 13$ 是存储区的数量，$1 \leq s \leq 13$ 是每个存储区可以存储的变量数。第二行包含一个非空程序，最多包含 $1 000$ 个用空格分隔的元素（每个 R$n$, V$i$ 和 E 都算作一个元素）。

你可以假设以下几点：

• 在重复 R$n$ 中，重复次数满足 $1 \leq n \leq 10^6$。
• 在循环操作 R$n$ <program> E 中，循环体 <program> 不为空。
• 在变量引用 V$i$ 中，变量索引满足 $1 \leq i \leq \min(b \times s, 13)$。
• 程序执行的总变量引用数最多为 $10^{12}$。

Output Format

显示完成程序所需执行的最小指令数。

翻译来自于：ChatGPT。

1 2
V1 V2 V1 V1 V2

5

2 1
V1 V2 V1 V1 V2

6

1 2
R10 V1 V2 V1 E

30

4 1
V1 R2 V2 V4 R2 V1 E V3 E

17