AT_joig2023_f タイピング大会 (Typing Contest)

在 JOIG 国家，人们使用 JOIG 语言。在 JOIG 语言中，共有 $15$ 种字符：`A`, `B`, `C`, `D`, `E`, `F`, `G`, `H`, `I`, `J`, `K`, `L`, `M`, `N`, `O`。 下个月将在 JOIG 国举行一次打字比赛，比拼使用 $15$ 种字符组成的长度为 $N$ 的字符串 $S$ 的输入所需时间。在本次比赛中，参赛者需遵循以下规则进行打字： - 参赛者只能用一根手指进行打字。 - 参赛者需使用一排按键呈一行排布、极为狭长的键盘，$15$ 个字符的键依次排在键盘上。每位参赛者可以自由决定各字符按键的具体排列顺序与位置。 - 参赛者需依次输入字符串 $S$ 的第 $1, 2, \dots, N$ 个字符。 本次比赛共有 $Q$ 位参赛者。不同参赛者的打字能力不同。第 $i$ 位参赛者（$1 \leq i \leq Q$）的打字规则如下： - 按下手指正下方的按键一次需要 $A_i$ 毫秒。 - 手指每向左移动一个按键需 $L_i$ 毫秒。 - 手指每向右移动一个按键需 $R_i$ 毫秒。 现给定字符串 $S$ 以及每位参赛者的数据，请你为每位参赛者求出，从开始输入 $S$ 第一个字符到打完最后一个字符的最短所需时间（单位：毫秒）。

输入按以下格式给出： > $N \ S \ Q$ > $A_1 \ L_1 \ R_1$ > $A_2 \ L_2 \ R_2$ > $\vdots$ > $A_Q \ L_Q \ R_Q$

输出共 $Q$ 行。第 $i$ 行（$1 \leq i \leq Q$）输出第 $i$ 位参赛者从开始输入 $S$ 第一个字符到打完最后一个字符的最短时间（单位：毫秒）。

## 子任务 1.（$2$ 分）字符串 $S$ 的每个字符均为 `A`，且 $Q = 1$。 2.（$3$ 分）字符串 $S$ 的每个字符均为 `A` 或 `B`，且 $Q = 1$。 3.（$4$ 分）字符串 $S$ 的每个字符均为 `A`、`B` 或 `C`，且 $Q = 1$。 4.（$9$ 分）字符串 $S$ 的每个字符为 `A`、`B`、`C`、`D`、`E`、`F`、`G`、`H` 之一，$Q = 1$，$N \leq 100$。 5.（$14$ 分）字符串 $S$ 的每个字符为 `A`、`B`、`C`、`D`、`E`、`F`、`G`、`H` 之一，$Q = 1$。 6.（$26$ 分）字符串 $S$ 的每个字符为 `A`、`B`、`C`、`D`、`E`、`F`、`G`、`H` 之一。 7.（$23$ 分）$Q = 1$。 8.（$7$ 分）$L_i = R_i$（$1 \leq i \leq Q$）。 9.（$12$ 分）无其他额外限制。 ## 样例说明 1 例如，考虑键盘从左到右依次排列为 `ONMLKJIHGFEDCBA`。此时，按照下表的操作，输入字符串 `ABAABB` 总共需要 $1\,110$ 毫秒。 | 步骤 | 操作 | 指下按键 | 用时（毫秒） | |-----|----------------|----------|------------| | 1 | 按下 A | A | 100 | | 2 | 向左移一位至 B | A → B | 150 | | 3 | 按下 B | B | 100 | | 4 | 向右移一位至 A | B → A | 210 | | 5 | 按下 A | A | 100 | | 6 | 按下 A | A | 100 | | 7 | 向左移一位至 B | A → B | 150 | | 8 | 按下 B | B | 100 | | 9 | 按下 B | B | 100 | 除了上述键盘排列外，也可能有其它能在 $1\,110$ 毫秒内完成输入的布局，但无法更快。因此，输出 $1\,110$。 此输入数据满足子任务 $2, 3, 4, 5, 6, 7, 9$ 的限制。 ## 样例说明 2 例如，考虑键盘从左到右依次排列为 `CABDEFGHIJKLMNO`。此时，按照下表的操作，输入字符串 `CBACAB` 总共需要 $2\,260$ 毫秒。 | 步骤 | 操作 | 指下按键 | 用时（毫秒） | |-----|----------------|----------|------------| | 1 | 按下 C | C | 150 | | 2 | 向右移一位至 A | C → A | 220 | | 3 | 向右移一位至 B | A → B | 220 | | 4 | 按下 B | B | 150 | | 5 | 向左移一位至 A | B → A | 240 | | 6 | 按下 A | A | 150 | | 7 | 向左移一位至 C | A → C | 240 | | 8 | 按下 C | C | 150 | | 9 | 向右移一位至 A | C → A | 220 | | 10 | 按下 A | A | 150 | | 11 | 向右移一位至 B | A → B | 220 | | 12 | 按下 B | B | 150 | 除了上述键盘排列外，也可能有其它能在 $2\,260$ 毫秒内完成输入的布局，但无法更快。因此，输出 $2\,260$。 此输入数据满足子任务 $3, 4, 5, 6, 7, 9$ 的限制。 ## 样例说明 3 由于需要连续输入 $20$ 次 `A`，无论键位如何排列，总时间为 $230\,000\,000 \times 20 = 4\,600\,000\,000$ 毫秒。因此，应输出 $4\,600\,000\,000$。 该输入数据满足所有子任务的限制。 ## 样例说明 4 本样例满足子任务 $6, 9$ 的限制。 ## 样例说明 5 本样例满足子任务 $8, 9$ 的限制。 # 数据范围与约定 - $1 \leq N \leq 1\,000\,000$。 - $S$ 是长度为 $N$ 的字符串。 - $S$ 的每个字符为 `A`, `B`, `C`, `D`, `E`, `F`, `G`, `H`, `I`, `J`, `K`, `L`, `M`, `N`, `O` 之一。 - $1 \leq Q \leq 150\,000$。 - $1 \leq A_i \leq 10^{11}$（$1 \leq i \leq Q$）。 - $1 \leq L_i \leq 10^{11}$（$1 \leq i \leq Q$）。 - $1 \leq R_i \leq 10^{11}$（$1 \leq i \leq Q$）。 - $N, Q, A_i, L_i, R_i$ 均为整数。 由 ChatGPT 5 翻译