CF2156B Strange Machine

有 $n$ 台机器按照环状排列，其中 $n$ 最多为 $20$。每台机器都是类型 A 或类型 B。机器按顺时针编号为 $1$ 至 $n$，第 $i$ 台机器的类型用 $s_i$ 表示。每台机器会对整数 $x$ 按其类型进行以下操作： - 类型 A：将 $x$ 减 $1$。形式为 $x := x - 1$。 - 类型 B：将 $x$ 替换为 $\left\lfloor\frac{x}{2}\right\rfloor$，即 $x := \left\lfloor\frac{x}{2}\right\rfloor$，这里 $\lfloor y\rfloor$ 表示 $y$ 的向下取整，也就是不大于 $y$ 的最大整数。 你会得到 $q$ 个询问，每个询问提供一个整数 $a$。对每个询问，从第 $1$ 台机器开始，手里持有整数 $a$。每一秒，按如下两步顺序执行： 1. 当前机器根据自身类型操作 $a$。 2. 顺时针移动到下一台机器： - 如果当前在机器 $i$（$1 \le i \le n - 1$），则移动到机器 $i+1$。 - 如果当前在机器 $n$，则回到机器 $1$。 该过程持续到 $a$ 变为 $0$。对于每个询问，计算 $a$ 变为 $0$ 需要的秒数。 注意所有询问互不影响。

每个测试用例包含多组数据。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。每组数据描述如下： 每组数据的第一行包含两个整数 $n$ 和 $q$（$1\le n\le 20$，$1\le q\le 10^4$），分别表示机器台数和询问数。 第二行是长度为 $n$ 的字符串 $s$（$|s| = n$ 且 $s_i =\mathtt{A}$ 或 $\mathtt{B}$），表示每台机器的类型。 第三行包含 $q$ 个整数 $a_1, a_2, \ldots, a_q$（$1\le a_i\le 10^9$），分别表示每个询问的起始整数。 特别地，对所有测试用例，$q$ 的总和不超过 $10^4$。

对于每组数据，输出 $q$ 个整数，分别对应每个询问的答案。

在第一个测试用例中，询问情况如下： - 询问 $1$：$a = 3$ 1. 从机器 $1$ 开始。机器 $1$ 将 $a$ 变为 $\left\lfloor\frac{3}{2}\right\rfloor = 1$。 2. 移动到机器 $2$。机器 $2$ 将 $a$ 减 $1$，变为 $1 - 1 = 0$。 因此 $a$ 变为 $0$ 共用 $2$ 秒。 - 询问 $2$：$a = 4$ 1. 从机器 $1$ 开始。机器 $1$ 将 $a$ 变为 $\left\lfloor\frac{4}{2}\right\rfloor = 2$。 2. 移动到机器 $2$。机器 $2$ 将 $a$ 减 $1$，变为 $2 - 1 = 1$。 3. 回到机器 $1$。机器 $1$ 将 $a$ 变为 $\left\lfloor\frac{1}{2}\right\rfloor = 0$。 因此 $a$ 变为 $0$ 共用 $3$ 秒。 在第二个测试用例中，唯一的询问起始 $a = 20$： 1. 从机器 $1$ 开始。机器 $1$ 将 $a$ 变为 $\left\lfloor\frac{20}{2}\right\rfloor = 10$。 2. 留在机器 $1$。机器 $1$ 将 $a$ 变为 $\left\lfloor\frac{10}{2}\right\rfloor = 5$。 3. 留在机器 $1$。机器 $1$ 将 $a$ 变为 $\left\lfloor\frac{5}{2}\right\rfloor = 2$。 4. 留在机器 $1$。机器 $1$ 将 $a$ 变为 $\left\lfloor\frac{2}{2}\right\rfloor = 1$。 5. 留在机器 $1$。机器 $1$ 将 $a$ 变为 $\left\lfloor\frac{1}{2}\right\rfloor = 0$。 因此 $a$ 变为 $0$ 共用 $5$ 秒。 由 ChatGPT 5 翻译